2010/04/27 by Yam Ki Cheung, Ovidiu Daescu, Cheung, Yam Ki +1
Computer Science · Engineering · #Advanced Numerical Analysis Techniques #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Robotic Path Planning Algorithms #cs.CG
paper · pdf · doi:10.48550/arxiv.1004.4901
24 pages 6 figures
arxiv created 2010/04/27 · openalex publication_date 2010/04/27 · arxiv updated 2010/04/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We discuss two versions of the Fréchet distance problem in weighted planar subdivisions. In the first one, the distance between two points is the weighted length of the line segment joining the points. In the second one, the distance between two points is the length of the shortest path between the points. In both cases, we give algorithms for finding a (1+epsilon)-factor approximation of the Fréchet distance between two polygonal curves. We also consider the Fréchet distance between two polygonal curves among polyhedral obstacles in R3 and present a (1+epsilon)-factor approximation algorithm.