### 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.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 28th Annual Symposuim on Computational Geometry, SCG 2012 |

Pages | 121-130 |

Number of pages | 10 |

DOIs | |

State | Published - Jul 23 2012 |

Event | 28th Annual Symposuim on Computational Geometry, SCG 2012 - Chapel Hill, NC, United States Duration: Jun 17 2012 → Jun 20 2012 |

### Publication series

Name | Proceedings of the Annual Symposium on Computational Geometry |
---|

### Other

Other | 28th Annual Symposuim on Computational Geometry, SCG 2012 |
---|---|

Country | United States |

City | Chapel Hill, NC |

Period | 6/17/12 → 6/20/12 |

### Fingerprint

### Keywords

- Approximation algorithms
- Frechét distance

### ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics

### Cite this

*Proceedings of the 28th Annual Symposuim on Computational Geometry, SCG 2012*(pp. 121-130). (Proceedings of the Annual Symposium on Computational Geometry). https://doi.org/10.1145/2261250.2261269