Мінімаксне спрощення кривих з гарантованою L∞-похибкою
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 f...
Gespeichert in:
| Datum: | 2026 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Vinnytsia National Technical University
2026
|
| Schlagworte: | |
| Online Zugang: | https://oeipt.vntu.edu.ua/index.php/oeipt/article/view/799 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Optoelectronic Information-Power Technologies |
Institution
Optoelectronic Information-Power Technologies| _version_ | 1856543906190065664 |
|---|---|
| author | Кривошея, М.І. Квєтний, Р.Н. |
| author_facet | Кривошея, М.І. Квєтний, Р.Н. |
| author_sort | Кривошея, М.І. |
| baseUrl_str | |
| collection | OJS |
| datestamp_date | 2026-01-12T10:58:28Z |
| description | 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. |
| first_indexed | 2026-02-08T08:10:40Z |
| format | Article |
| id | oai:oeipt.vntu.edu.ua:article-799 |
| institution | Optoelectronic Information-Power Technologies |
| language | Ukrainian |
| last_indexed | 2026-02-08T08:10:40Z |
| publishDate | 2026 |
| publisher | Vinnytsia National Technical University |
| record_format | ojs |
| spelling | oai:oeipt.vntu.edu.ua:article-7992026-01-12T10:58:28Z Minimax curve simplification with guaranteed L∞ error Мінімаксне спрощення кривих з гарантованою L∞-похибкою Кривошея, М.І. Квєтний, Р.Н. minimax approximation L∞ Hausdorff curve simplification RDP parametric search computer vision мінімаксна апроксимація L∞ Hausdorff спрощення кривих RDP параметричний пошук комп’ютерний зір 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. У цій роботі запропоновано метод спрощення/апроксимації кривих, який за фіксованого бюджету примітивів m мінімізує максимальну геометричну похибку (односторонню Hausdorff або евклідову відстань до сегментів). Ядро підходу: ми підбираємо мінімальне ε (граничне відхилення), використовуючи бінарний пошук і швидку перевірку: чи можна покрити послідовні точки відрізком так, щоб усі вони лежали в «смужці» шириною ε навколо цього відрізка. Додатково відрізки локально підлаштовуються так, щоб помилка всередині кожного з них була рівномірною й без великих «піків». Експерименти показують, що за однакового бюджету сегментів наш метод дає меншу максимальну похибку, ніж евристика Ramer–Douglas–Peucker. Подано чіткий протокол оцінювання та робочий Python-прототип. Vinnytsia National Technical University 2026-01-12 Article Article application/pdf https://oeipt.vntu.edu.ua/index.php/oeipt/article/view/799 10.31649/1681-7893-2025-50-2-73-78 Optoelectronic Information-Power Technologies; Vol. 50 No. 2 (2025); 73-78 Оптико-електроннi iнформацiйно-енергетичнi технологiї; Том 50 № 2 (2025); 73-78 Оптико-електроннi iнформацiйно-енергетичнi технологiї; Том 50 № 2 (2025); 73-78 2311-2662 1681-7893 10.31649/1681-7893-2025-50-2 uk https://oeipt.vntu.edu.ua/index.php/oeipt/article/view/799/728 |
| spellingShingle | мінімаксна апроксимація L∞ Hausdorff спрощення кривих RDP параметричний пошук комп’ютерний зір Кривошея, М.І. Квєтний, Р.Н. Мінімаксне спрощення кривих з гарантованою L∞-похибкою |
| title | Мінімаксне спрощення кривих з гарантованою L∞-похибкою |
| title_alt | Minimax curve simplification with guaranteed L∞ error |
| title_full | Мінімаксне спрощення кривих з гарантованою L∞-похибкою |
| title_fullStr | Мінімаксне спрощення кривих з гарантованою L∞-похибкою |
| title_full_unstemmed | Мінімаксне спрощення кривих з гарантованою L∞-похибкою |
| title_short | Мінімаксне спрощення кривих з гарантованою L∞-похибкою |
| title_sort | мінімаксне спрощення кривих з гарантованою l∞-похибкою |
| topic | мінімаксна апроксимація L∞ Hausdorff спрощення кривих RDP параметричний пошук комп’ютерний зір |
| topic_facet | minimax approximation L∞ Hausdorff curve simplification RDP parametric search computer vision мінімаксна апроксимація L∞ Hausdorff спрощення кривих RDP параметричний пошук комп’ютерний зір |
| url | https://oeipt.vntu.edu.ua/index.php/oeipt/article/view/799 |
| work_keys_str_mv | AT krivošeâmí minimaxcurvesimplificationwithguaranteedlerror AT kvêtnijrn minimaxcurvesimplificationwithguaranteedlerror AT krivošeâmí mínímaksnesproŝennâkrivihzgarantovanoûlpohibkoû AT kvêtnijrn mínímaksnesproŝennâkrivihzgarantovanoûlpohibkoû |