Мінімаксне спрощення кривих з гарантованою L∞-похибкою
DOI:
https://doi.org/10.31649/1681-7893-2025-50-2-73-78Ключові слова:
мінімаксна апроксимація, L∞, Hausdorff, спрощення кривих, RDP, параметричний пошук, комп’ютерний зірАнотація
У цій роботі запропоновано метод спрощення/апроксимації кривих, який за фіксованого бюджету примітивів m мінімізує максимальну геометричну похибку (односторонню Hausdorff або евклідову відстань до сегментів). Ядро підходу: ми підбираємо мінімальне ε (граничне відхилення), використовуючи бінарний пошук і швидку перевірку: чи можна покрити послідовні точки відрізком так, щоб усі вони лежали в «смужці» шириною ε навколо цього відрізка. Додатково відрізки локально підлаштовуються так, щоб помилка всередині кожного з них була рівномірною й без великих «піків». Експерименти показують, що за однакового бюджету сегментів наш метод дає меншу максимальну похибку, ніж евристика Ramer–Douglas–Peucker. Подано чіткий протокол оцінювання та робочий Python-прототип.
Посилання
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
##submission.downloads##
-
PDF
Завантажень: 0
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:- Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.
- Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.
- Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).
