Document Open Access Logo

Homotopic Curve Shortening and the Affine Curve-Shortening Flow

Authors Sergey Avvakumov, Gabriel Nivasch

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2020.12.pdf
  • Filesize: 0.54 MB
  • 15 pages

Document Identifiers

Author Details

Sergey Avvakumov
  • Institute of Science and Technology Austria (IST Austria), Am Campus 1, 3400 Klosterneuburg, Austria
Gabriel Nivasch
  • Ariel University, Ariel, Israel

Funding

  • Avvakumov, Sergey: Supported by the Austrian Science Fund (FWF), Project P31312-N35.

Acknowledgements

Thanks to Arseniy Akopyan, Imre Bárány, Jeff Erickson, Radoslav Fulek, Jeremy Schiff, Arkadiy Skopenkov, and Peter Synak for useful discussions. Thanks also to the referees for their useful comments.

Cite AsGet BibTex

Sergey Avvakumov and Gabriel Nivasch. Homotopic Curve Shortening and the Affine Curve-Shortening Flow. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SoCG.2020.12

Abstract

We define and study a discrete process that generalizes the convex-layer decomposition of a planar point set. Our process, which we call homotopic curve shortening (HCS), starts with a closed curve (which might self-intersect) in the presence of a set P⊂ ℝ² of point obstacles, and evolves in discrete steps, where each step consists of (1) taking shortcuts around the obstacles, and (2) reducing the curve to its shortest homotopic equivalent. We find experimentally that, if the initial curve is held fixed and P is chosen to be either a very fine regular grid or a uniformly random point set, then HCS behaves at the limit like the affine curve-shortening flow (ACSF). This connection between HCS and ACSF generalizes the link between "grid peeling" and the ACSF observed by Eppstein et al. (2017), which applied only to convex curves, and which was studied only for regular grids. We prove that HCS satisfies some properties analogous to those of ACSF: HCS is invariant under affine transformations, preserves convexity, and does not increase the total absolute curvature. Furthermore, the number of self-intersections of a curve, or intersections between two curves (appropriately defined), does not increase. Finally, if the initial curve is simple, then the number of inflection points (appropriately defined) does not increase.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Mathematics of computing → Geometric topology
Keywords
  • affine curve-shortening flow
  • shortest homotopic path
  • integer grid
  • convex-layer decomposition

Metrics

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

Related Versions

Supplementary Materials

References

  1. Hugo A. Akitaya, Radoslav Fulek, and Csaba D. Tóth. Recognizing weak embeddings of graphs. In Proc. 29th Symp. on Discrete Algorithms, pages 274-292, 2018. URL: https://doi.org/10.1137/1.9781611975031.20.
  2. Steven J. Altschuler and Matthew A. Grayson. Shortening space curves and flow through singularities. J. Differential Geom., 35(2):283-298, 1992. URL: https://doi.org/10.4310/jdg/1214448076.
  3. Luis Alvarez, Frédéric Guichard, Pierre-Luis Lions, and Jean-Michel Morel. Axioms and fundamental equations of image processing. Arch. Rational Mech. Anal., 123(3):199-257, 1993. URL: https://doi.org/10.1007/BF00375127.
  4. Sigurd Angenent. Parabolic equations for curves on surfaces: Part II. Intersections, blow-up and generalized solutions. Annals of Mathematics, 133(1):171-215, 1991. URL: https://doi.org/10.2307/2944327.
  5. Sigurd Angenent, Guillermo Sapiro, and Allen Tannenbaum. On the affine heat equation for non-convex curves. J. Amer. Math. Soc., 11(3):601-634, 1998. URL: https://doi.org/10.1090/S0894-0347-98-00262-8.
  6. Vic Barnett. The ordering of multivariate data. J. Roy. Statist. Soc. Ser. A, 139(3):318-355, 1976. URL: https://doi.org/10.2307/2344839.
  7. Sergei Bespamyatnikh. Computing homotopic shortest paths in the plane. Journal of Algorithms, 49(2):284-303, 2003. URL: https://doi.org/10.1016/S0196-6774(03)00090-7.
  8. George D. Birkhoff. Dynamical systems with two degrees of freedom. Trans. Amer. Math. Soc., 18:199-300, 1917. Google Scholar
  9. Sergio Cabello, Yuanxin Liu, Andrea Mantler, and Jack Snoeyink. Testing homotopy for paths in the plane. Discrete & Computational Geometry, 31(1):61-81, 2004. URL: https://doi.org/10.1007/s00454-003-2949-y.
  10. Frédéric Cao. Geometric Curve Evolution and Image Processing, volume 1805 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 2003. URL: https://doi.org/10.1007/b10404.
  11. Hsien-Chih Chang and Jeff Erickson. Untangling planar curves. Discrete & Computational Geometry, 58:889-920, 2017. URL: https://doi.org/10.1007/s00454-017-9907-6.
  12. Bernard Chazelle. A theorem on polygon cutting with applications. In Proc. 23rd Annual Symposium on Foundations of Computer Science (FOCS 1982), pages 339-349, 1982. URL: https://doi.org/10.1109/SFCS.1982.58.
  13. Bernard Chazelle. On the convex layers of a planar set. IEEE Trans. Inform. Theory, 31(4):509-517, 1985. URL: https://doi.org/10.1109/TIT.1985.1057060.
  14. Kai-Seng Chou and Xi-Ping Zhu. The Curve Shortening Problem. Chapman & Hall/CRC, Boca Raton, FL, 2001. URL: https://doi.org/10.1201/9781420035704.
  15. Cristopher B. Croke. Area and the length of the shortest closed geodesic. J. Differential Geometry, 27:1-21, 1988. Google Scholar
  16. Ketan Dalal. Counting the onion. Random Struct. Algor., 24(2):155-165, 2004. URL: https://doi.org/10.1002/rsa.10114.
  17. William F. Eddy. Convex Hull Peeling. In COMPSTAT 1982 5th Symposium held at Toulouse 1982, pages 42-47. Physica-Verlag, 1982. URL: https://doi.org/10.1007/978-3-642-51461-6_4.
  18. Alon Efrat, Stephen G. Kobourov, and Anna Lubiw. Computing homotopic shortest paths efficiently. Computational Geometry, 35(3):162-172, 2006. URL: https://doi.org/10.1016/j.comgeo.2006.03.003.
  19. David Eppstein, Sariel Har-Peled, and Gabriel Nivasch. Grid peeling and the affine curve-shortening flow. Experimental Mathematics, page to appear, 2018. URL: https://doi.org/10.1080/10586458.2018.1466379.
  20. Radoslav Fulek and Csaba D. Tóth. Crossing minimization in perturbed drawings. In T. Biedl and A. Kerren, editors, Proc. 26th Symp. Graph Drawing and Network Visualization, pages 229-241. Springer, 2018. URL: https://doi.org/10.1007/978-3-030-04414-5_16.
  21. Michael Gage and Richard S. Hamilton. The heat equation shrinking convex plane curves. J. Differential Geom., 23(1):69-96, 1986. URL: https://doi.org/10.4310/jdg/1214439902.
  22. Matthew A. Grayson. The heat equation shrinks embedded plane curves to round points. J. Differential Geom., 26(2):285-314, 1987. URL: https://doi.org/10.4310/jdg/1214441371.
  23. Matthew A. Grayson. Shortening embedded curves. Annals of Mathematics, 129(1):79-111, 1989. Google Scholar
  24. Sariel Har-Peled and Bernard Lidický. Peeling the grid. SIAM J. Discrete Math., 27(2):650-655, 2013. URL: https://doi.org/10.1137/120892660.
  25. Joel Hass and Peter Scott. Shortening curves on surfaces. Topology, 33:25-43, 1994. URL: https://doi.org/10.1016/0040-9383(94)90033-7.
  26. John Hershberger and Jack Snoeyink. Computing minimum length paths of a given homotopy class. Computational Geometry, 4(2):63-97, 1994. URL: https://doi.org/10.1016/0925-7721(94)90010-8.
  27. Der-Tsai Lee and Franco P. Preparata. Euclidean shortest paths in the presence of rectilinear barriers. Networks, 14(3):393-410, 1984. URL: https://doi.org/10.1002/net.3230140304.
  28. Guillermo Sapiro and Allen Tannenbaum. Affine invariant scale-space. Int. J. Comput. Vision, 11(1):25-44, 1993. URL: https://doi.org/10.1007/bf01420591.
  29. Brian White. Evolution of curves and surfaces by mean curvature. In Proceedings of the International Congress of Mathematicians, Vol. I (Beijing, 2002), pages 525-538, 2002. URL: https://www.mathunion.org/fileadmin/ICM/Proceedings/ICM2002.1/ICM2002.1.ocr.pdf.
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 Imprint Privacy Contact