LIPIcs.SoCG.2024.76.pdf
- Filesize: 1.36 MB
- 18 pages
Document
Grid Peeling of Parabolas
Authors
Günter Rote 
,
Morteza Saghafian
-
Part of:
Volume:
40th International Symposium on Computational Geometry (SoCG 2024)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2024-06-06
File
Document Identifiers
Author Details
Acknowledgements
Part of this work was done while G.R. enjoyed the hospitality of the Institute of Science and Technology Austria (ISTA) as a visiting professor during his sabbatical in the winter semester 2022/23.
Cite AsGet BibTex
Günter Rote, Moritz Rüber, and Morteza Saghafian. Grid Peeling of Parabolas. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 76:1-76:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
https://doi.org/10.4230/LIPIcs.SoCG.2024.76
https://doi.org/10.4230/LIPIcs.SoCG.2024.76
Abstract
Grid peeling is the process of repeatedly removing the convex hull vertices of the grid points that lie inside a given convex curve. It has been conjectured that, for a more and more refined grid, grid peeling converges to a continuous process, the affine curve-shortening flow, which deforms the curve based on the curvature. We prove this conjecture for one class of curves, parabolas with a vertical axis, and we determine the value of the constant factor in the formula that relates the two processes.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Discretization
Keywords
- grid polygons
- curvature flow
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- 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:199-257, 1993. URL: https://doi.org/10.1007/BF00375127.
- Sergey Avvakumov and Gabriel Nivasch. Homotopic curve shortening and the affine curve-shortening flow. Journal of Computational Geometry, 12:145-177, 2021. URL: https://doi.org/10.20382/jocg.v12i1a7.
- Imre Bárány, Matthieu Fradelizi, Xavier Goaoc, Alfredo Hubard, and Günter Rote. Random polytopes and the wet part for arbitrary probability distributions. Annales Henri Lebesgue, 3:701-715, 2020. URL: https://doi.org/10.5802/ahl.44.
- Imre Bárány and David G. Larman. Convex bodies, economic cap coverings, random polytopes. Mathematika, 35:274-291, 1988. URL: https://doi.org/10.1112/S0025579300015266.
- Jeff Calder and Charles K. Smart. The limit shape of convex hull peeling. Duke Mathematical Journal, 169(11):2079-2124, 2020. URL: https://doi.org/10.1215/00127094-2020-0013.
- Frédéric Cao. Geometric Curve Evolution and Image Processing, volume 1805 of Lecture Notes in Mathematics. Springer, Berlin, Heidelberg, 2003. URL: https://doi.org/10.1007/b10404.
- Travis Dillon and Narmada Varadarajan. Explicit bounds for the layer number of the grid, 2023. URL: https://arxiv.org/abs/2302.04244.
- David Eppstein, Sariel Har-Peled, and Gabriel Nivasch. Grid peeling and the affine curve-shortening flow. Experimental Mathematics, 29(3):306-316, 2020. URL: https://doi.org/10.1080/10586458.2018.1466379.
- Sariel Har-Peled and Bernard Lidický. Peeling the grid. SIAM Journal on Discrete Mathematics, 27(2):650-655, 2013. URL: https://doi.org/10.1137/120892660.
- The On-Line Encyclopedia of Integer Sequences. URL: http://oeis.org/.
- Guillermo Sapiro and Allen Tannenbaum. Affine invariant scale-space. Int. J. Comput. Vision, 11:25-44, 1993. URL: https://doi.org/10.1007/bf01420591.
- Guillermo Sapiro and Allen Tannenbaum. On affine plane curve evolution. Journal of Functional Analysis, 119(1):79-120, 1994. URL: https://doi.org/10.1006/jfan.1994.1004.
- J. Sándor and A. V. Kramer. Über eine zahlentheoretische Funktion. Mathematica Moravica, 3:53-62, 1999. URL: http://www.moravica.ftn.kg.ac.rs/Vol_3/10-Sandor-Kramer.pdf.