Name
Abstract | ||
|---|---|---|
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 point-wall pairs, 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 under most models, but that some restrictive assumptions do allow polynomial-time reconstruction algorithms. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.tcs.2010.10.026 | Theoretical Computer Science |
Keywords | Field | DocType |
polynomial-time reconstruction algorithm,present algorithmic,reconstruction problem,Reconstruction,floor plan,polygonal room,point-wall pair,Algorithm,different type,scanner data,Polygon,additional information,hardness result,point-normal pair,Covering,Reconstructing polygon | Computer vision,Polygon,Visibility,Reconstruction problem,Simply connected space,Polygon (computer graphics),Computer science,Floor plan,Artificial intelligence,Scanner,Simple polygon | Journal |
Volume | Issue | ISSN |
412 | 32 | Theoretical Computer Science |
Citations | PageRank | References |
10 | 0.84 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Therese Biedl | 1 | 902 | 106.36 |
| Stephane Durocher | 2 | 342 | 42.89 |
| Jack Snoeyink | 3 | 2842 | 231.68 |