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.

The video opens with a city scene, to be scanned by the robot. This gives rise to the AGP, introduced in the next sequence. Then an IP approach for general point guards is presented, based on an analysis of possible guard and witness positions in the arrangement of visibility polygons. This is followed by the description of an LP approach, which is combined with ideas for eliminating fractional vertices by means of cutting planes; the method is then applied to the city instance from the introduction. Finally, the resulting scans are combined into a virtual ight through the city environment, both in visible light and in infrared.

This video belongs to the 22nd Annual Video and Multimedia Review of Computational Geometry, which is part of the 29th Annual Symposium on Computational Geometry.