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.
翻译:矩形多边形是一个多边形,其边缘是轴对齐的。在多边形边界上逆时针反向走,产生左转和右转的序列。左转的次数总是等于右转+4的数目。已知任何这样的序列都可以通过直线多边形实现。在本文中,我们考虑的是找到能够最大限度地缩小多边形周边或区域或多边形边框区域或多边形边框区域的认识的问题。我们显示所有三个问题一般都是NP硬的。这回答了Patrignani [CGTA 2001] 的开放问题,后者显示,要将一个给定平面图的圆形图的边框最小化是NP-硬的。我们还表明,用最小约束框区域实现多边线是NP-硬的。然后我们考虑的是$x$-mononoone和$xy$-monononoone 矩形多边形的特例。对于这三个目标,我们可以有效地优化三个目标。