How to Walk Your Dog in the Mountains with No Magic Leash
How to Walk Your Dog in the Mountains with No Magic Leash
复制标题
如何在没有魔法皮带的情况下在山里遛狗
DOI：
--
复制
发表时间：
2012
影响因子：
0.8
通讯作者：
Anastasios Sidiropoulos
中科院分区：
文献类型：
--
作者：
Sariel Har;A. Nayyeri;M. Salavatipour;Anastasios Sidiropoulos
我们描述了一个O(Logn)\DocumentClass[12pt]{minimum}\usepackage{amsath}\usepackage{wa ysym}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathsfs}\usepackage{upgreek}\setlong{\oddsidemarin}{-69pt}\Begin{Document}$$O(\logn)$$\end{Document}-计算位于三角拓扑盘边界上的两条多边形曲线之间同伦Fréchet距离的近似算法。在这项工作之前，人们所知的算法只适用于欧几里得平面上带有多边形障碍物的曲线。我们分析中的一个关键技术成分是O(Logn)\Documentclass[12pt]{Minimum}\usepackage{amsath}\usepackage{wa ysym}\usepackage{amsfonts}\usepackage{amsbsy}\usepackage{mathsfs}\usepackage{upgreek}\setlong{\oddsidemargin}{-69pt}\Begin{Document}$$O(\log n)$$\end{Document}-用于计算两条曲线之间同伦的最小高度的近似算法。在此之前，还没有已知的算法可以逼近这个参数。令人惊讶的是，甚至不知道计算同伦Fréchet距离或同伦的最小高度是否在NP中。
We describe a O(logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\log n )$$\end{document}-approximation algorithm for computing the homotopic Fréchet distance between two polygonal curves that lie on the boundary of a triangulated topological disk. Prior to this work, algorithms were known only for curves on the Euclidean plane with polygonal obstacles. A key technical ingredient in our analysis is a O(logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\log n)$$\end{document}-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 Fréchet distance, or the minimum height of a homotopy, is in NP.