05649438

a

05649438 Biedl, Therese Durocher, Stephane Snoeyink, Jack Reconstructing polygons from scanner data. Dong, Yingfei (ed.) et al., Algorithms and computation. 20th international symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16--18, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-10630-9/pbk). Lecture Notes in Computer Science 5878, 862-871 (2009). 2009 Berlin: Springer EN

doi:10.1007/978-3-642-10631-6_87

Summary: A range-finding scanner can collect information about the shape of an (unknown) polygonal room in which it is placed. Suppose that a set of scanners returns not only a set of points, but also additional information, such as the normal to the plane when a scan beam detects a wall. We consider the problem of reconstructing the floor plan of a room from different types of scan data. In particular, we present algorithmic and hardness results for reconstructing two-dimensional polygons from points, point/normal pairs, and visibility polygons. The polygons may have restrictions on topology (e.g., to be simply connected) or geometry (e.g., to be orthogonal). We show that this reconstruction problem is NP-hard in most models, but for some assumptions allows polynomial-time reconstruction algorithms which we describe.