Loading...
Please wait, while we are loading the content...
Similar Documents
How to walk your dog in the mountains with no magic leash (2011).
| Content Provider | CiteSeerX |
|---|---|
| Author | Har-Peled, Sariel Nayyeri, Amir Salavatipour, Mohammad Sidiropoulos, Anastasios |
| Abstract | We describe a O(log n)-approximation algorithm for computing the homotopic Frechét distance between two polygonal curves that lie on the boundary of a triangulated topological disk. Prior to this work, algorithms where known only for curves on the Euclidean plane with polygonal obstacles. A key technical ingredient in our analysis is a O(log n)-approximation algorithm for computing the minimum height of a homotopy between two curves. No algorithms were previously known for approximating this parameter. Surprisingly, it is not even known if computing either the homotopic Frechét distance, or the minimum height of a homotopy, is in NP. 1 |
| File Format | |
| Publisher Date | 2011-01-01 |
| Access Restriction | Open |
| Subject Keyword | Magic Leash Minimum Height Approximation Algorithm Homotopic Frech Distance Euclidean Plane Polygonal Obstacle Key Technical Ingredient Polygonal Curve Triangulated Topological Disk |
| Content Type | Text |
