Point Guards and Point Clouds: Solving General Art Gallery Problems

Abstract

In this video, we illustrate how one of the classical areas of computational geometry has gained in practical relevance, which in turn gives rise to new, fascinating geometric problems. In particular, we demonstrate how the robot platform IRMA3D can produce high-resolution, virtual 3D environments, based on a limited number of laser scans. Computing an optimal set of scans amounts to solving an instance of the Art Gallery Problem (AGP): Place a minimum number of stationary guards in a polygonal region P, such that all points in P are guarded.

Publication
Proceedings of the Twenty-ninth Annual Symposium on Computational Geometry