Time complexity of two disjoint simple paths

Finding two disjoint simple paths on two given sets of points is a geometric problem introduced by Jeff Erickson. This problem has various applications in computational geometry, like robot motion planning, generating polygon etc. We will present a reduction from planar Hamiltonian path to this problem, and prove that it is NP-Complete. To the best of our knowledge, no study has considered its complexity up until now. We also present a reduction from planar Hamiltonian path problem to the problem of “finding a path on given points in the presence of arbitrary obstacles” and prove that it is NP-Complete too. Also, we present a heuristic algorithm with time complexity of O(n^4) to solve this problem. The proposed algorithm first calculates the convex hull for each of the entry points and then produces two simple paths on the two entry point sets.