# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Minimum Rectilinear Polygons for Given Angle Sequences

##### MPS-Authors

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)

arXiv:1606.06940.pdf

(Preprint), 3MB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

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

##### 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. 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.

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.