  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.
