There are $N$ points inside a polygon. If two points are connected by an edge (a line segment) if the edge is completely inside the polygon. We could conclude finding a Hamiltonian path is NPC, but what about non-intersecting Hamiltonian path?

  • $\begingroup$ What's the definition of visibility? Is the polygon convex? $\endgroup$ – xskxzr Aug 7 at 7:00
  • $\begingroup$ Two points are visible mutually if the line segment connecting them is completely inside the polygon. Every visible pair of points are connected. No it isn't necessary to be convex.In convex polygons the answer is always yes and can be found in O(nlogn) $\endgroup$ – inaderi Aug 7 at 7:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.