Premium
Euclidean shortest path in the presence of obstacles
Author(s) -
Chen YongMao,
Ramanan Prakash
Publication year - 1991
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230210302
Subject(s) - combinatorics , monotone polygon , mathematics , shortest path problem , path (computing) , line segment , disjoint sets , line (geometry) , euclidean shortest path , spanning tree , binary logarithm , point (geometry) , plane (geometry) , graph , longest path problem , computer science , geometry , programming language
Abstract We consider the problem of finding the (Euclidean) shortest path SP(s, t) between two points s and t in the plane, in the presence of obstacles. Lee and Preparata considered a special case, where the obstacles are n disjoint segments parallel to the y ‐axis. Let V be the set consisting of s, t and the endpoints of the n segments. They showed that the shortest path between s and any point in V is monotone with respect to the x ‐axis. Let SPT(V) denote the Shortest Path Tree on V that consists of the shortest path from s to each point in V . They presented an O ( n log n ) algorithm for constructing SPT(V) and an Ω( n log n ) lower bound for finding SP(s, t) . Their algorithm first sorts the segments according to their abscissae and then constructs SPT(V) by sweeping a vertical line from s to t . Their lower bound proof is based on the fact that any algorithm that finds SP(s, t) must actually sort the segments according to their abscissae. We prove that even if the segments are given in sorted order of their abscissae, Ω( n log n ) time is still required to find SPT(V) . The sweep‐line technique for finding SP(s, t) can be used whenever SP(s, t) is monotone. Lee and Preparata stated that SP(s, t) is monotone for arbitrary obstacles, if the projections of any two obstacles on the x ‐axis do not overlap. We prove that SP(s, t) is monotone if the projections of any two obstacles do not partially overlap, and s and t are, respectively, to the left and to the right of all the obstacles.