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 excluding the line segments from polygon's 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.
I am looking for constructive example.
If I understand the question correctly, it is impossible. From each polygon vertex there are three outgoing lines: two edges of the polygon, and one given line segment. They are going in three different axis-parallel directions.
Now consider 45-degree slanted lines in the plane (southwest to northeast). Take the highest such line that touches one of the polygon vertices. From that vertex you can only draw 2 axis-parallel lines (east and south), because otherwise you would have vertices above the line, which would contradict the choice of the line. So you cannot have the three axis-parallel lines.
