Document Open Access Logo

Computing Optimal Homotopies over a Spiked Plane with Polygonal Boundary

Authors Benjamin Burton, Erin Chambers, Marc van Kreveld, Wouter Meulemans, Tim Ophelders, Bettina Speckmann

PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.23.pdf
  • Filesize: 0.77 MB
  • 14 pages

Document Identifiers

Author Details

Benjamin Burton
Erin Chambers
Marc van Kreveld
Wouter Meulemans
Tim Ophelders
Bettina Speckmann

Cite As Get BibTex

Benjamin Burton, Erin Chambers, Marc van Kreveld, Wouter Meulemans, Tim Ophelders, and Bettina Speckmann. Computing Optimal Homotopies over a Spiked Plane with Polygonal Boundary. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ESA.2017.23

Abstract

Computing optimal deformations between two curves is a fundamental question with various applications, and has recently received much attention in both computational topology and in mathematics in the form of homotopies of disks and annular regions. In this paper, we examine this problem in a geometric setting, where we consider the boundary of a polygonal domain with spikes, point obstacles that can be crossed at an additive cost. We aim to continuously morph from one part of the boundary to another, necessarily passing over all spikes, such that the most expensive intermediate curve is minimized, where the cost of a curve is its geometric length plus the cost of any spikes it crosses.

We first investigate the general setting where each spike may have a different cost. For the number of inflection points in an intermediate curve, we present a lower bound that is linear in the number of spikes, even if the domain is convex and the two boundaries for which we seek a morph share an endpoint. We describe a 2-approximation algorithm for the general case, and an optimal algorithm for the case that the two boundaries for which we seek a morph share both endpoints, thereby representing the entire boundary of the domain.

We then consider the setting where all spikes have the same unit cost and we describe a polynomial-time exact algorithm. The algorithm combines structural properties of homotopies arising from the geometry with methodology for computing Fréchet distances.

Subject Classification

Keywords
  • Fréchet distance
  • polygonal domain
  • homotopy
  • geodesic
  • obstacle

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Helmut Alt and Michael Godau. Computing the Fréchet distance between two polygonal curves. International Journal on Computational Geometry and Application, 5(1-2):75-91, 1995. Google Scholar
  2. Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, and Vincenzo Roselli. Morphing planar graph drawings optimally. In Automata, Languages, and Programming (ICALP), LNCS 8572, pages 126-137, 2014. Google Scholar
  3. Patrizio Angelini, Fabrizio Frati, Maurizio Patrignani, and Vincenzo Roselli. Morphing planar graph drawings efficiently. In Graph Drawing, volume 8242 of LNCS 8242, pages 49-60, 2013. Google Scholar
  4. Graham R. Brightwell and Peter Winkler. Submodular percolation. SIAM Journal on Discrete Mathematics, 23(3):1149-1178, 2009. Google Scholar
  5. Erin W. Chambers, Gregory R. Chambers, Arnaud de Mesmay, Tim Ophelders, and Regina Rotman. Monotone contractions of the boundary of the disc. Computing Research Repository (arXiv):1704.06175, 2017. Google Scholar
  6. Erin W. Chambers, Éric Colin de Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus, and Shripad Thite. Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time. Computational Geometry: Theory and Applications, 43(3):295-311, 2010. Google Scholar
  7. Erin W. Chambers and David Letscher. On the height of a homotopy. In Proceedings of the 21st Canadian Conference on Computational Geometry, pages 103-106, 2009. Google Scholar
  8. Erin W. Chambers and Mikael Vejdemo-Johansson. Computing minimum area homologies. Computer Graphics Forum, 34(6):13-21, 2015. Google Scholar
  9. Erin W. Chambers and Yusu Wang. Measuring similarity between curves on 2-manifolds via homotopy area. In Proceedings of the 29th Annual Symposium on Computational Geometry, pages 425-434, 2013. Google Scholar
  10. Gregory R. Chambers. Optimal Homotopies of Curves on Surfaces. PhD thesis, University of Toronto, Canada, 2014. Google Scholar
  11. Gregory R. Chambers and Yevgeny Liokumovich. Converting homotopies to isotopies and dividing homotopies in half in an effective way. Geometric and Functional Analysis, 24(4):1080-1100, 2014. Google Scholar
  12. Gregory R. Chambers and Regina Rotman. Monotone homotopies and contracting discs on Riemannian surfaces. Journal of Topology and Analysis, 2016. Google Scholar
  13. Atlas F. Cook and Carola Wenk. Geodesic Fréchet distance inside a simple polygon. ACM Transactions on Algorithms, 7(1):Art. 9, 2009. Google Scholar
  14. Tamal K. Dey, Anil N. Hirani, and Bala Krishnamoorthy. Optimal homologous cycles, total unimodularity, and linear programming. SIAM Journal on Computing, 40(4):1026-1044, 2011. Google Scholar
  15. Alon Efrat, Quanfu Fan, and Suresh Venkatasubramanian. Curve matching, time warping, and light fields: New algorithms for computing similarity between curves. Journal of Mathematical Imaging and Vision, 27(3):203-216, 2007. URL: http://dx.doi.org/10.1007/s10851-006-0647-0.
  16. Alon Efrat, Leonidas J. Guibas, Sariel Har-Peled, Joseph S. B. Mitchell, and T. M. Murali. New similarity measures between polylines with applications to morphing and polygon sweeping. Discrete & Computational Geometry, 28(4):535-569, 2002. Google Scholar
  17. Brittany Fasy, Selcuk Karakoç, and Carola Wenk. On minimum area homotopies. In Computational Geometry: Young Researchers Forum, pages 49-50, 2016. Google Scholar
  18. Sariel Har-Peled, Amir Nayyeri, Mohammad Salavatipour, and Anastasios Sidiropoulos. How to walk your dog in the mountains with no magic leash. In Proceedings of the 28th Annual Symposium on Computational Geometry, pages 121-130, 2012. Google Scholar
  19. Zipei Nie. On the minimum area of null homotopies of curves traced twice. Computing Research Repository (arXiv):1412.0101, 2014. Google Scholar
  20. Godfried Toussaint. An optimal algorithm for computing the relative convex hull of a set of points in a polygon. School of Computer Science, McGill University, 1986. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact