Covering points with orthogonal polygons ?
We address the problem of covering points with orthogonal polygons. Specifically, given a set of n n points in the plane, we investigate the existence of an orthogonal polygon such that there is a one-to-one correspondence between the points and the edges of the polygon. In an earlier paper, we have shown that constructing such a covering with an orthogonally convex  polygon, if any, can be done in O(nlogn) O ( n log n ) time. In case an orthogonally convex polygon cannot cover the point set, we show in this paper that the problem of deciding whether such a point set can be covered with any orthogonal polygon is NP-complete. The problem remains NP-complete even if the orientations of the edges covering each point are specified in advance as part of the input.
covering orthogonal polygon np-completeness