An efficient PILP algorithm for 3D region guarding and star decomposition
Wuyi Yu, Xin Shane Li · 2011
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.