Reconstructing generalized staircase polygons with uniform step length

DOI10.1007/978-3-319-73915-1_8MaRDI QIDQ4625103zbMATH OpenOpenAlexFDO

Authors Nodari Sitchinava, Darren Strash

Publication date 20 February 2019

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.09842

zbMATH Keywords

fixed-parameter tractabilityorthogonal polygonspolygon reconstructionvisibility graph recognitionvisibility graphs

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: 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(n^{2}m)$-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^{2}m)$ under reasonable alignment restrictions.

Recommendations

• Reconstructing generalized staircase polygons with uniform step length
• Orthogonal polygon reconstruction from stabbing information
• VISIBILITY GRAPHS OF STAIRCASE POLYGONS WITH UNIFORM STEP LENGTH
• Visibility Graphs of Anchor Polygons
• POINT AND LINE SEGMENT RECONSTRUCTION FROM VISIBILITY INFORMATION

Cites work

• Characterizing and recognizing the visibility graph of a funnel-shaped polygon
• Efficient and secure authenticated key exchange using weak passwords
• Graph isomorphism in quasipolynomial time (extended abstract)
• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 2081084 (Why is no real title available?)
• scientific article; zbMATH DE number 1424307 (Why is no real title available?)
• Introduction to modern cryptography
• Number-theoretic constructions of efficient pseudo-random functions
• On characterizing terrain visibility graphs
• Orthogonal polygon reconstruction from stabbing information
• Recognizing visibility graphs of spiral polygons
• Reconstructing generalized staircase polygons with uniform step length
• Theory of Cryptography
• Visibility graphs of staircase polygons and the weak Bruhat order. I: From visibility graphs to maximal chains
• VISIBILITY GRAPHS OF STAIRCASE POLYGONS WITH UNIFORM STEP LENGTH

Cited in

(6)

• Orthogonal polygon reconstruction from stabbing information
• Foundations for analytical models of staircase traversal of convex polygonal surfaces
• Reconstructing generalized staircase polygons with uniform step length
• POINT AND LINE SEGMENT RECONSTRUCTION FROM VISIBILITY INFORMATION
• Reconstructing generalized staircase polygons with uniform step length
• VISIBILITY GRAPHS OF STAIRCASE POLYGONS WITH UNIFORM STEP LENGTH

This page was built for publication: Reconstructing generalized staircase polygons with uniform step length

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4625103)