This is a follow-up on my pervious post.

Given a set of N rectilinear line segments on 2N distinct points (with integer coordinates) on a square grid. Can we find a rectilinear polygon that passes through the endpoints of the N line segments while including all given line segments on polygon's sides?

Also, I am interested in the case where a subset of the line segments is used as polygon sides.

The 2N points are the only vertices of the polygon. Rectilinear polygon means all its angles are right angles (the sides are parallel to the coordinate axes). The given line segments are axis-parallel.


1 Answer 1


Perhaps I missed something, but as I understand the answer is no (we cannot always find such a polygon). For example, if you have two line segments, one from $(0,0)$ to $(1,0)$, and the other from $(2,1)$ to $(3,1)$, you only have four vertices for the polygon. How could you connect the two $y=0$ vertices (both have $x \le 1$) to the two $y=1$ vertices (both have $x \ge 2$) with vertical or horizontal edges?

So, what did I miss?


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .