Approximate Euclidean Shortest Paths amid Polygonal Obstacles
R. Inkulu, Sanjiv Kapoor · arXiv (Cornell University) · 2015
Given a set \mathcal{P} of non-intersecting polygonal obstacles in \mathbb{R}^2 defined with n vertices, we compute a sketch \Omega of \mathcal{P} whose size is independent of n. We utilize \Omega to devise an algorithm to compute a (1+\epsilon)-approximate Euclidean shortest path between two points given with the description of \mathcal{P}. When \mathcal{P} comprises of convex polygonal obstacles, we devise a (2+\epsilon)-approximation algorithm to efficiently answer two-point Euclidean distance queries.