Geodesic Fréchet Distance with Polygonal Obstacles

Date
2008-07
Authors
Cook, Atlas F. IV
Wenk, Carola
Journal Title
Journal ISSN
Volume Title
Publisher
UTSA Department of Computer Science
Abstract

We present the first algorithm to compute the geodesic Fréchet distance between two polygonal curves in a plane with polygonal obstacles, where distances between points are measured as the length of a shortest path between them. Using shortest path structures that we call dynamic and static spotlights, we efficiently construct and propagate reachability information through the free space diagram to solve the Fréchet distance. We also show how to construct a novel shortest path map from a line segment source (instead of from a point source). This shortest path map supports geodesic distance queries from any point s ∈ ab to any point t ∈ cd in optimal logarithmic time and permits the shortest path to be reported in output-sensitive fashion.

Description
Keywords
Citation
Department
Computer Science