Geodesic Fréchet Distance with Polygonal Obstacles
| dc.contributor.author | Cook, Atlas F. IV | |
| dc.contributor.author | Wenk, Carola | |
| dc.date.accessioned | 2023-10-24T15:55:56Z | |
| dc.date.available | 2023-10-24T15:55:56Z | |
| dc.date.issued | 2008-07 | |
| dc.description.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. | |
| dc.description.department | Computer Science | |
| dc.description.sponsorship | This work has been supported by the National Science Foundation grant NSF CAREER CCF-0643597. | |
| dc.format.extent | 1 online resource (10 pages) | |
| dc.identifier.uri | https://hdl.handle.net/20.500.12588/2144 | |
| dc.language.iso | en_US | |
| dc.publisher | UTSA Department of Computer Science | |
| dc.relation.ispartofseries | Technical Report; CS-TR-2008-010 | |
| dc.subject.lcsh | Polygons | |
| dc.subject.lcsh | Fréchet spaces | |
| dc.subject.lcsh | Geodesics (Mathematics) | |
| dc.subject.lcsh | Algorithms | |
| dc.title | Geodesic Fréchet Distance with Polygonal Obstacles | |
| dc.type | Technical Report |