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
    Commented Aug 7, 2019 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
    Commented Aug 7, 2019 at 7:40
  • $\begingroup$ Please see: pdfs.semanticscholar.org/62b6/… $\endgroup$
    – HEKTO
    Commented Aug 22, 2019 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
    Commented Aug 23, 2019 at 7:16


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.