Article,
Minimum Rectilinear Polygons for Given Angle Sequences
Computational Geometry: Theory and Applications, 100 (101820): 1--39 (2022)
DOI: 10.1016/j.comgeo.2021.101820
Abstract
A rectilinear polygon is a simple 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
four. 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 a polyline within a
bounding box of minimum area (or within a fixed
given rectangle) 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.
