Help Privacy Policy Disclaimer
  Advanced SearchBrowse





Minimum Rectilinear Polygons for Given Angle Sequences

There are no MPG-Authors in the publication available
External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 3MB

Supplementary Material (public)
There is no public supplementary material available

Evans, W. S., Fleszar, K., Kindermann, P., Saeedi, N., Shin, C.-S., & Wolff, A. (2018). Minimum Rectilinear Polygons for Given Angle Sequences. Retrieved from http://arxiv.org/abs/1606.06940.

Cite as: https://hdl.handle.net/21.11116/0000-0002-E5A6-0
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. Then we consider the special cases of $x$-monotone and
$xy$-monotone rectilinear polygons. For these, we can optimize the three
objectives efficiently.
The former version of this paper had inaccuracies in the NP-hardness proof
which have been now addressed.