2017/08/31 by Nodari Sitchinava, Sitchinava, Nodari, Darren Strash +1
Computer Science · Engineering · #Computational Geometry and Mesh Generation #Computer Graphics and Visualization Techniques #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.2 #Robotics and Sensor-Based Localization #cs.DS
paper · pdf · doi:10.48550/arxiv.1708.09842
Appears in the Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017)
openalex publication_date 2017/08/31 · arxiv created 2017/09/01 · arxiv updated 2017/09/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Visibility graph reconstruction, which asks us to construct a polygon that has a given visibility graph, is a fundamental problem with unknown complexity (although visibility graph recognition is known to be in PSPACE). We show that two classes of uniform step length polygons can be reconstructed efficiently by finding and removing rectangles formed between consecutive convex boundary vertices called tabs. In particular, we give an O(n2m)-time reconstruction algorithm for orthogonally convex polygons, where n and m are the number of vertices and edges in the visibility graph, respectively. We further show that reconstructing a monotone chain of staircases (a histogram) is fixed-parameter tractable, when parameterized on the number of tabs, and polynomially solvable in time O(n2m) under reasonable alignment restrictions.