Given a setX of points in the plane, two distinguished pointss;t2X ,a nd as et of obstacles represented by line segments, we wish to compute a simple polygonal path froms tot that uses only points inX as vertices and avoids the obstacles in. We present two results: (1) we show that finding such simple paths among arbitrary obstacles is NP-complete, and (2) we give a polynomial-time algorithm that computes simple paths when the obstacles form a simple polygonP andX is insideP . Our algorithm runs in time O.m 2 n 2 / ,w herem is the number of vertices ofP andn is the number of points inX. © 2000 Elsevier Science B.V. All rights reserved.
['Qi Cheng', 'Marek Chrobak', 'Gopalakrishnan Sundaram']
Computing simple paths among obstacles