1984/09/01 by D. T. Lee, F. P. Preparata · 1 citation
Computer Science · #Computational Geometry and Mesh Generation #Data Management and Algorithms #Robotic Path Planning Algorithms
paper · doi:10.1002/net.3230140304
crossref issued 1984/09/01 · crossref published 1984/09/01 · crossref published-print 1984/09/01 · openalex publication_date 1984/09/01 · crossref published-online 2006/10/11 · crossref created 2007/05/11 · crossref deposited 2023/10/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11 · crossref indexed 2026/07/30
Abstract In this paper we address the problem of constructing a Euclidean shortest path between two specified points (source, destination) in the plane, which avoids a given set of barriers. This problem had been solved earlier for polygonal obstacles with the aid of the visibility graph. This approach however, has an Ω(n 2 ) time lower bound, if n is the total number of vertices of the obstacles. Our goal is to find interesting cases for which the solution can be obtained without the explicit construction of the entire visibility graph. The two cases are (i) the path must lie within an n‐vertex simple polygon; (ii) the obstacles are n disjoint and parallel line segments. In both instances greedy O(n log n) time algorithms can be developed which solve the problems by constructing the shortest‐path tree from the source to all the vertices of the obstacles and to the destination.