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 '19 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 '19 at 7:40
  • $\begingroup$ Please see: pdfs.semanticscholar.org/62b6/… $\endgroup$ – HEKTO Aug 22 '19 at 23:27
  • $\begingroup$ Unfortunately this paper has two ambiguous parts which seems to be wrong:First in the end of page three Actually [12] doesn't give a method like this. [12] finds simple paths from s to t using given points, but not two non crossing paths.([12] doesn't even claim it finds all the path) And also in the part called Handling internal points: We can construct an example in which a point is not visible by both ends(vertices) of any of it's surrounding polygon segments.And as a result we cant connect it to the polygon. It is in contrast with the claim that we can add all the internal points . $\endgroup$ – inaderi Aug 23 '19 at 7:16

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.