TY - JOUR
ID - 4116
TI - Time complexity of two disjoint simple paths
JO - Scientia Iranica
JA - SCI
LA - en
SN - 1026-3098
AU - Razzazi, M.
AU - Sepahvand, A.
AD - Department of Computer Engineering and Information Technology, Amirkabir University of Technology, Tehran, P.O. Box
15875-4413, Iran
Y1 - 2017
PY - 2017
VL - 24
IS - 3
SP - 1335
EP - 1343
KW - Hamiltonian path
KW - NP-complete
KW - Planar graph
KW - Simple path
DO - 10.24200/sci.2017.4116
N2 - Finding two disjoint simple paths on two given sets of points is a geometric problem introduced by Je Erickson. This problem has various applications in computational geometry, e.g. robot motion planning, generating polygon, etc. We willm present a reduction from planar Hamiltonian path to this problem, and prove that it is NPcomplete. 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 \nding a path on given points in the presence of arbitrary obstacles" and prove that it is also NP-complete. Also, we present a heuristic algorithm with time complexity of O(n4) to solve this problem. The proposed algorithm rst calculates the convex hull for each of the entry points and then produces two simple paths on the two entry point sets.
UR - https://scientiairanica.sharif.edu/article_4116.html
L1 - https://scientiairanica.sharif.edu/article_4116_eb58976172267e329120321fe7774f09.pdf
ER -