Minimax curve simplification with guaranteed L∞ error

Authors

  • M.I. Kryvosheia Vinnytsia National Technical University
  • R.N. Kvyetnyy Vinnytsia National Technical University

DOI:

https://doi.org/10.31649/1681-7893-2025-50-2-73-78

Keywords:

minimax approximation, L∞, Hausdorff, curve simplification, RDP, parametric search, computer vision

Abstract

This paper proposes a curve simplification/approximation method that, for a fixed budget of primitives m, minimizes the maximum geometric error (one-sided Hausdorff or Euclidean distance to segments). The core idea is to find the minimal admissible ε (error bound) via binary search together with a fast feasibility check: can a consecutive block of points be covered by a single segment so that all points lie within an  ε-wide “tube” around that segment? In addition, segments are locally adjusted so that the error within each segment is as uniform as possible, avoiding large spikes. Experiments show that, for the same segment budget, our method achieves a smaller maximum error than the Ramer–Douglas–Peucker heuristic. We also provide a clear evaluation protocol and a working Python prototype.

Author Biographies

M.I. Kryvosheia, Vinnytsia National Technical University

аспірант

R.N. Kvyetnyy, Vinnytsia National Technical University

доктор  технічних наук, професор,

References

Ramer, U. An iterative procedure for polygonal approximation of plane curves. Computer Graphics and Image Processing, 1(3), 244–256, 1972.

https://scholar.google.com/scholar?q=Ramer+1972+polygonal+approximation

Douglas, D. H., Peucker, T. K. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. The Canadian Cartographer, 10(2), 112–122, 1973.

https://scholar.google.com/scholar?q=Douglas+Peucker+1973

Visvalingam, M., Whyatt, J. D. Line generalisation by repeated elimination of points. The Cartographic Journal, 30(1), 46–51, 1993. https://scholar.google.com/scholar?q=Visvalingam+Whyatt+1993

Imai, H., Iri, M. Polygonal approximation of a curve—formulations and algorithms. In: Computational Morphology (Eds. G. T. Toussaint), North-Holland, 71–86, 1988.

https://scholar.google.com/scholar?q=Imai+Iri+1988+computational+morphology

Alt, H., Godau, M. Computing the Fréchet distance between two polygonal curves. International Journal of Computational Geometry & Applications, 5(1–2), 75–91, 1995.

https://scholar.google.com/scholar?q=Alt+Godau+1995

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

https://scholar.google.com/scholar?q=Eiter+Mannila+1994+discrete+Frechet

Chebyshev, P. L. Théorie des mécanismes connus sous le nom de parallélogrammes. Mémoires de l'Académie Impériale des Sciences de St-Pétersbourg, 7, 539–568, 1859.

https://scholar.google.com/scholar?q=Chebyshev+1859+parallélogrammes

Remez, E. Sur une méthode de calcul des polynômes d’approximation de Tchebycheff. Comptes Rendus de l’Académie des Sciences, 199, 337–340, 1934.

https://scholar.google.com/scholar?q=Remez+1934+Tchebycheff

Hausdorff, F. Grundzüge der Mengenlehre. Leipzig: Veit, 1914.

https://scholar.google.com/scholar?q=Hausdorff+Grundzüge+1914

Belkin, M., Hsu, D., Ma, S., Mandal, S. Reconciling modern machine learning practice and the classical bias–variance trade-off. Proceedings of the National Academy of Sciences (PNAS), 116(32), 15849–15854, 2019. https://scholar.google.com/scholar?q=Belkin+Hsu+Ma+Mandal+2019

Lafon, M., Thomas, A. Understanding the Double Descent Phenomenon in Deep Learning. arXiv preprint arXiv:2403.10459, 2024.

https://scholar.google.com/scholar?q=Lafon+Thomas+Double+Descent+2024

de Berg, M., Cheong, O., van Kreveld, M., Overmars, M. Computational Geometry: Algorithms and Applications, 3rd ed. Springer, 2008.

https://scholar.google.com/scholar?q=de+Berg+Cheong+van+Kreveld+Overmars+2008

M. Kryvosheia Investigation of the Double Descent Phenomenon and Comparison of Minimax Approximation with L2 Regularization Optoelectronic Information-Power Technologies 49 № 1 (2025) https://doi.org/10.31649/1681-7893-2025-49-1

Downloads

Abstract views: 0

Published

2026-01-12

How to Cite

[1]
M. Kryvosheia and R. Kvyetnyy, “Minimax curve simplification with guaranteed L∞ error”, Опт-ел. інф-енерг. техн., vol. 50, no. 2, pp. 73–78, Jan. 2026.

Issue

Vol. 50 No. 2 (2025)

Section

OptoElectronic/Digital Methods and Systems for Image/Signal Processing

Metrics

Downloads

Download data is not yet available.

License

Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:

  1. Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.
  2. Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.
  3. Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).