%0 Conference Paper %1 efkssw-mrpga-JCDCGG15 %A Evans, William S. %A Fleszar, Krzysztof %A Kindermann, Philipp %A Saeedi, Noushin %A Shin, Chan-Su %A Wolff, Alexander %B Proceedings of the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG’15) %D 2015 %I Springer-Verlag %K myown %P 105--119 %R 10.1007/978-3-319-48532-4_10 %T Minimum Rectilinear Polygons for Given Angle Sequences %V 9943 %X 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.

@inproceedings{efkssw-mrpga-JCDCGG15, 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.}, added-at = {2015-09-10T15:05:38.000+0200}, arxiv = {https://arxiv.org/abs/1606.06940}, author = {Evans, William S. and Fleszar, Krzysztof and Kindermann, Philipp and Saeedi, Noushin and Shin, Chan-Su and Wolff, Alexander}, biburl = {https://www.bibsonomy.org/bibtex/2c0ca3a9c9ab39944d85def7de88048db/kindermann}, booktitle = {Proceedings of the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG’15)}, doi = {10.1007/978-3-319-48532-4_10}, interhash = {8075a240defe5bda9be16bd30e742a32}, intrahash = {c0ca3a9c9ab39944d85def7de88048db}, keywords = {myown}, month = sep, pages = {105--119}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, slides = {http://www1.pub.informatik.uni-wuerzburg.de/pub/kindermann/slides/2015-jcdcgg-lrsequence-chansu.pdf}, timestamp = {2021-02-11T15:32:12.000+0100}, title = {Minimum Rectilinear Polygons for Given Angle Sequences}, volume = 9943, year = 2015 }