“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:
