An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane

An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane

0.00 Avg rating0 Votes
Article ID: iaor19981324
Country: United States
Volume: 18
Issue: 4
Start Page Number: 377
End Page Number: 383
Publication Date: Dec 1997
Journal: Discrete and Computational Geometry
Authors: , ,
Keywords: geometry
Abstract:

We give an algorithm to compute a (Euclidean) shortest path in a polygon with h holes and a total of n vertices. The algorithm uses O(n) space and requires O(n+h2log n) time.

Reviews

Required fields are marked *. Your email address will not be published.