# Can we find a rectilinear polygon that excludes a set of N line segments?

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.

• What other requirements do you have for that rectilinear polygon? It passes through those $2N$ endpoints but can it have other vertices too? Do the other vertices have to be at integer coordinates? Sep 10, 2021 at 14:20
• @JukkaKohonen I edited the post. Sep 10, 2021 at 14:26
• Thanks. Rectilinear polygon means all its angles are right angles? Or also that the sides are parallel to the coordinate axes? Are the given line segments also axis-parallel? Sep 10, 2021 at 14:28
• @JukkaKohonen I would relax to your suggestion if there is a proof that my original requirements can not be met? Sep 10, 2021 at 14:29
• It's certainly impossible without further assumptions. Consider the case of $N$ line segments with end points $(j,0)$ and $(j,1)$ where $1 \le j \le N$. Sep 10, 2021 at 14:32 