Reconstructing Generalized Staircase Polygons with Uniform Step Length
DOI:
https://doi.org/10.7155/jgaa.00469Keywords:
visibility graphs , polygon reconstruction , visibility graph recognition , orthogonal polygons , fixed-parameter tractabilityAbstract
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). As far as we are aware, the only class of orthogonal polygons that are known to have efficient reconstruction algorithms is the class of orthogonal convex fans (staircase polygons) with uniform step lengths. 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(n^2m)$-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(n^2m)$ under alignment restrictions. As a consequence of our reconstruction techniques, we also get recognition algorithms for visibility graphs of these classes of polygons with the same running times.Downloads
Download data is not yet available.
Downloads
Published
2018-09-01
How to Cite
Sitchinava, N., & Strash, D. (2018). Reconstructing Generalized Staircase Polygons with Uniform Step Length. Journal of Graph Algorithms and Applications, 22(3), 431–459. https://doi.org/10.7155/jgaa.00469
Issue
Section
Articles
Categories
License
Copyright (c) 2018 Nodari Sitchinava, Darren Strash
This work is licensed under a Creative Commons Attribution 4.0 International License.