“An efficient PILP algorithm for 3D region guarding and star decomposition” by Yu and Li
Conference:
Type(s):
Title:
- An efficient PILP algorithm for 3D region guarding and star decomposition
Presenter(s)/Author(s):
Abstract:
We propose an efficient algorithm to compute 3D region guarding and star decomposition. A star decomposition partitions a 3D region to a set of sub-regions, each of which is visible from an interior point and is called a star shape. Star decomposition is closely related to the well known gallery guarding problem [Chvatal 1975]. Despite their broad applications in graphics and robotics, 3D region guarding and star decomposition are highly challenging and have been little explored.
References:
1. Chvatal, V. 1975. A combinatorial theorem in plane geometry. Journal of Combinatorial Theory Series B 18, 39–41.
2. Lien, J.-M. 2007. Approximate star-shaped decomposition of point set data. In Eurographics Symposium on Point-Based Graphics, 1–8.
Additional Images:
![©Wuyi Yu and Xin Li](https://history.siggraph.org/wp-content/uploads/2024/02/2011-Poster-Yu_An-Efficient-PILP-Algorithm-for-3D-Region-Guarding-and-Star-Decomposition-03.png)
![©Wuyi Yu and Xin Li](https://history.siggraph.org/wp-content/uploads/2024/02/2011-Poster-Yu_An-Efficient-PILP-Algorithm-for-3D-Region-Guarding-and-Star-Decomposition-04.png)
![©Wuyi Yu and Xin Li](https://history.siggraph.org/wp-content/uploads/2024/02/2011-Poster-Yu_An-Efficient-PILP-Algorithm-for-3D-Region-Guarding-and-Star-Decomposition-05.png)
![©Wuyi Yu and Xin Li](https://history.siggraph.org/wp-content/uploads/2024/02/2011-Poster-Yu_An-Efficient-PILP-Algorithm-for-3D-Region-Guarding-and-Star-Decomposition-06.png)
![©Wuyi Yu and Xin Li](https://history.siggraph.org/wp-content/uploads/2024/02/2011-Poster-Yu_An-Efficient-PILP-Algorithm-for-3D-Region-Guarding-and-Star-Decomposition-07.png)