Minimum rectilinear polygons for given angle sequences

DOI10.1007/978-3-319-48532-4_10MaRDI QIDQ2958091zbMATH OpenOpenAlexFDO

Authors Krzysztof Fleszar, Philipp Kindermann, Noushin Saeedi, Chan-Su Shin, Alexander Wolff, W. Evans

Publication date 1 February 2017

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

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: A rectilinear polygon is a polygon whose edges are axis-aligned. Walking counterclockwise on the boundary of such a polygon yields a sequence of left turns and right turns. The number of left turns always equals the number of right turns plus 4. It is known that any such sequence can be realized by a rectilinear polygon. In this paper, we consider the problem of finding realizations that minimize the perimeter or the area of the polygon or the area of the bounding box of the polygon. We show that all three problems are NP-hard in general. This answers an open question of Patrignani [CGTA 2001], who showed that it is NP-hard to minimize the area of the bounding box of an orthogonal drawing of a given planar graph. We also show that realizing polylines with minimum bounding box area is NP-hard. Then we consider the special cases of $x$-monotone and $xy$-monotone rectilinear polygons. For these, we can optimize the three objectives efficiently.

Recommendations

• Area bounds of rectilinear polygons realized by angle sequences
• Area Bounds of Rectilinear Polygons Realized by Angle Sequences
• scientific article; zbMATH DE number 4049401
• Minimum k-partitioning of rectilinear polygons
• Complexities of efficient solutions of rectilinear polygon cover problems

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A polygon is determined by its angles
• An improved algorithm for reconstructing a simple polygon from its visibility angles
• Area Bounds of Rectilinear Polygons Realized by Angle Sequences
• Drawing polygons given angle sequences
• Minimum rectilinear polygons for given angle sequences
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• On the complexity of orthogonal compaction
• Reconstructing polygons from scanner data
• Rectilinear Graphs and Their Embeddings

Cited in

(10)

• Minimum rectilinear polygons for given angle sequences
• Minimum rectilinear polygons for given angle sequences
• Polygons with prescribed angles in 2D and 3D
• Minimum area polygons with two reflex angles enclosingkPoints
• scientific article; zbMATH DE number 2062589 (Why is no real title available?)
• Area bounds of rectilinear polygons realized by angle sequences
• On Turn-Regular Orthogonal Representations
• Area Bounds of Rectilinear Polygons Realized by Angle Sequences
• Minimum degree triangulation for rectangular domains
• MINIMUM POLYGON TRANSVERSALS OF LINE SEGMENTS

This page was built for publication: Minimum rectilinear polygons for given angle sequences

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