article

How to Walk Your Dog in the Mountains with No Magic Leash

Authors:

Sariel Har-Peled,

Mohammad Salavatipour,

Anastasios SidiropoulosAuthors Info & Claims

Discrete & Computational Geometry, Volume 55, Issue 1

Pages 39 - 73

https://doi.org/10.1007/s00454-015-9737-3

Published: 01 January 2016 Publication History

Abstract

We describe a $$O(\log n )$$O(logn)-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(\log n)$$O(logn)-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.

References

[1]

Agarwal, P.K., Aronov, B., O'Rourke, J., Schevon, C.A.: Star unfolding of a polytope with applications. SIAM J. Comput. 26, 1679---1713 (1997)

[2]

Alt, H., Buchin, M.: Semi-computability of the Fréchet distance between surfaces. In: Proceedings of the 21st European Workshop on Computational Geometry, pp. 45---48 (2005)

[3]

Alt, H., Godau, M.: Computing the Fréchet distance between two polygonal curves. Int. J. Comput. Geom. Appl. 5, 75---91 (1995)

[4]

Bennis, C., Vézien, J.-M., Iglésias, G., Gagalowicz, A.: Piecewise surface flattening for non-distorted texture mapping. In: Sederberg, T.W. (ed). Proceedings of SIGGRAPH '91, vol. 25, pp. 237---246. ACM, New York (1991)

Digital Library

[5]

Brakatsoulas, S., Pfoser, D., Salas, R., Wenk, C.: On map-matching vehicle tracking data. In: Proceedings of 31st VLDB Conference, VLDB Endowment, pp. 853---864. Norwegian University of Science & Technology, Trondheim (2005)

[6]

Brightwell, G.A., Winkler, P.: Submodular percolation. SIAM J. Discrete Math. 23(3), 1149---1178 (2009)

Digital Library

[7]

Buchin, K., Buchin, M., Gudmundsson, J.: Detecting single file movement. In: Proceedings of 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS), pp. 288---297. ACM, New York (2008)

[8]

Buchin, K., Buchin, M., Gudmundsson, J., Maarten, L., Luo, J.: Detecting commuting patterns by clustering subtrajectories. In: Proceedings of the 19th International Symposium on Algorithms and Computation (ISAAC), pp. 644---655. Springer, Heidelberg (2008)

[9]

Buchin, M., Driemel, A., Speckmann, B.: Computing the Fréchet distance with shortcuts is NP-hard. In: Proceedings of the 30th Annual Symposium on Computational Geometry SOCG'14 (Kyoto, Japan), pp. 367---376. ACM, New York, NY (2014)

[10]

Chambers, E.W., Letscher, D.: On the height of a homotopy. In: Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG), pp. 14. University of British Columbia, Vancouver (2009)

[11]

Chambers, E.W., Letscher, D.: Erratum for on the height of a homotopy. http://mathcs.slu.edu/~chambers/papers/hherratum.pdf (2010)

[12]

Chambers, G.R., Rotman, R.: Contracting loops on a Riemannian 2-surface (2013). arXiv:1311.2995

[13]

Chambers, E.W., Wang, Y.: Measuring similarity between curves on 2-manifolds via homotopy area. In: Proceedings of the 29th Annual Symposium on Computational Geometry (SoCG), pp. 425---434. ACM, New York (2013)

[14]

Chambers, E.W., Colin de Verdière, E., Erickson, J., Lazard, S., Lazarus, F., Thite, S.: Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time. Comput. Geom. Theory Appl. 43(3), 295---311 (2010)

Digital Library

[15]

Chambers, E.W., Letscher, D., Ju, T., Liu, L.: Isotopic Fréchet distance. In: Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG), pp. 229---234. CCCG, Toronto (2011)

[16]

Cook, A.F., Wenk, C.: Geodesic Fréchet distance inside a simple polygon. ACM Trans. Algorithms 7, 9:1---9:19 (2010)

Digital Library

[17]

Cook, A.F., Wenk, C.: Shortest path problems on a polyhedral surface. Algorithmica 69(1), 58---77 (2014)

[18]

Cook, A.F., Driemel, A., Har-Peled, S., Sherette, J., Wenk, C.: Computing the Fréchet distance between folded polygons. In: Proceedings of the 12th Workshop Algorithms Data Structure (WADS), pp. 267---278. Springer, Berlin (2011)

[19]

Driemel, A., Har-Peled, S., Wenk, C.: Approximating the Fréchet distance for realistic curves in near linear time. Discrete Comput. Geom. 48, 94---127 (2012)

[20]

Efrat, A., Guibas, L.J., Har-Peled, S., Mitchell, J.S.B., Murali, T.M.: New similarity measures between polylines with applications to morphing and polygon sweeping. Discrete Comput. Geom. 28, 535---569 (2002)

Digital Library

[21]

Eiter, T., Mannila, H.: Computing discrete Fréchet distance. Technical Report CD-TR 94/64, Christian Doppler Laboratory for Expert Systems, TU, Vienna (1994)

[22]

Floater, M.S.: Parameterization and smooth approximation of surface triangulations. Comput. Aided Geom. Des. 14(4), 231---250 (1997)

Digital Library

[23]

Frechét, M.: Sur la distance de deux surfaces. Ann. Soc. Polonaise Math. 3, 4---19 (1924)

[24]

Godau, M.: On the complexity of measuring the similarity between geometric objects in higher dimensions. PhD Thesis, Free University of Berlin (1999)

[25]

Har-Peled, S., Raichel, B.: The Fréchet distance revisited and extended. In: Proceedings of the 27th Annual Symposium on Computational Geometry (SoCG), pp. 448---457. ACM Press, New York (2011)

[26]

Har-Peled, S., Nayyeri, A., Salavatipour, M., Sidiropoulos, A.: How to walk your dog in the mountains with no magic leash. In: Proceedings of the 28th Annual ACM Symposium on Computational Geometry (SoCG), pp. 121---130. ACM, New York (2012)

[27]

Henzinger, M.R., Klein, P., Rao, S., Subramanian, S.: Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci. 55, 3---23 (1997)

Digital Library

[28]

Keogh, E.J., Pazzani, M.J.: Scaling up dynamic time warping to massive dataset. In: Proceedings of the Third European Conference on Principles of Data Mining and Knowledge Discovery, pp. 1---11. Springer, Prague (1999)

Digital Library

[29]

Kim, M.S., Kim, S.W., Shin, M.: Optimization of subsequence matching under time warping in time-series databases. In: Proceedings of the ACM Symposium on Applied Computing, pp. 581---586. ACM, New York (2005)

[30]

Lewis, P.M., II, Stearns, R.E., Hartmanis, J.: Memory bounds for recognition of context-free and context-sensitive languages. In: Proceedings of the 6th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 191---202. ACM, New York (1965)

[31]

Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36, 177---189 (1979)

Digital Library

[32]

Mascret, A., Devogele, T., Le Berre, I., Hénaff, A.: Coastline matching process based on the discrete Fréchet distance. In: Proceedings of the 12th International Symposium on Spatial Data Handling, pp. 383---400. Springer, Berlin (2006)

[33]

Mitchell, J.S.B., Mount, D.M., Papadimitriou, C.H.: The discrete geodesic problem. SIAM J. Comput. 16, 647---668 (1987)

Digital Library

[34]

Papasoglu, P.: Contracting thin disks (2013). arXiv:1309.2967

[35]

Piponi, D., Borshukov, G.: Seamless texture mapping of subdivision surfaces by model pelting and texture blending. In: Proceedings of the SIGGRAPH 2000, pp. 471---478. ACM, New York (2000)

[36]

Serrà, J., Gómez, E., Herrera, P., Serra, X.: Chroma binary similarity and local alignment applied to cover song identification. IEEE Trans. Audio Speech Lang. Process. 16(6), 1138---1151 (2008)

Digital Library

[37]

Sheffer, A., de Sturler, E.: Surface parameterization for meshing by triangulation flattening. In: Proceedings of the 9th International Meshing Roundtable, pp. 161---172. Springer, Berlin (2000)

[38]

Sherette, J., Wenk, C.: Simple curve embedding. CoRR (2013). arXiv:1303.0821

[39]

Wenk, C., Salas, R., Pfoser, D.: Addressing the need for map-matching speed: Localizing global curve-matching algorithms. In: Proceedings of the 18th Conference on Scientific and Statistical Database Management, pp. 879---888. Springer, Berlin (2006)

Cited By

Biedl TChambers EEppstein DDe Mesmay AOphelders T(2019)Homotopy Height, Grid-Major Height and Graph-Drawing HeightGraph Drawing and Network Visualization10.1007/978-3-030-35802-0_36(468-481)Online publication date: 17-Sep-2019
https://dl.acm.org/doi/10.1007/978-3-030-35802-0_36
Chambers Ede Mesmay AOphelders TCzumaj A(2018)On the complexity of optimal homotopiesProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175343(1121-1134)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175343
Chang HErickson JLetscher Dde Mesmay ASchleimer SSedgwick EThurston DTillmann SCzumaj A(2018)Tightening curves on surfaces via local movesProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175274(121-135)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175274

How to Walk Your Dog in the Mountains with No Magic Leash
1. Computing methodologies
  1. Computer graphics
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

How to walk your dog in the mountains with no magic leash
SoCG '12: Proceedings of the twenty-eighth annual symposium on Computational geometry

We describe a O(log n)-approximation algorithm for computing the homotopic Frechet 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 ...
Computing the Fréchet Distance with a Retractable Leash

All known algorithms for the Fréchet distance between curves proceed in two steps: first, they construct an efficient oracle for the decision version; second, they use this oracle to find the optimum from a finite set of critical values. We present a ...
A PTAS for the horizontal rectangle stabbing problem
Abstract
We study rectangle stabbing problems in which we are given n axis-aligned rectangles in the plane that we want to stab, that is, we want to select line segments such that for each given rectangle there is a line segment that intersects two ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Discrete & Computational Geometry

Discrete & Computational Geometry Volume 55, Issue 1

January 2016

248 pages

ISSN:0179-5376

Issue’s Table of Contents

Copyright © Copyright © 2016 Springer Science+Business Media New York.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 January 2016

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Biedl TChambers EEppstein DDe Mesmay AOphelders T(2019)Homotopy Height, Grid-Major Height and Graph-Drawing HeightGraph Drawing and Network Visualization10.1007/978-3-030-35802-0_36(468-481)Online publication date: 17-Sep-2019
https://dl.acm.org/doi/10.1007/978-3-030-35802-0_36
Chambers Ede Mesmay AOphelders TCzumaj A(2018)On the complexity of optimal homotopiesProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175343(1121-1134)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175343
Chang HErickson JLetscher Dde Mesmay ASchleimer SSedgwick EThurston DTillmann SCzumaj A(2018)Tightening curves on surfaces via local movesProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175274(121-135)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175274

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents