Abstract
We consider the problem of simplifying curves under the Fréchet distance. Let P be a curve and ε ≥ 0 be a distance threshold. An ε-simplification is a curve within Fréchet distance ε of P . We consider ε-simplifications of minimum complexity (i.e. minimum number of vertices). Parameterized by ε, we define a continuous family of minimum complexity ε-simplifications P ε of a curve P in
one dimension. We present a data structure that after linear preprocessing time can report the ε-simplification in linear output-sensitive time. Moreover, for k ≥ 1, we show how this data structure can be used to report a simplification P ε with at most k vertices that is closest to P in O(k) time.
one dimension. We present a data structure that after linear preprocessing time can report the ε-simplification in linear output-sensitive time. Moreover, for k ≥ 1, we show how this data structure can be used to report a simplification P ε with at most k vertices that is closest to P in O(k) time.
| Original language | English |
|---|---|
| Pages | 62:1-62:6 |
| Number of pages | 6 |
| Publication status | Published - 29 Mar 2023 |
| Event | The 39th European Workshop on Computational Geometry - Universitat Politècnica de Catalunya, Barcelona, Spain Duration: 29 Mar 2023 → 31 Mar 2023 Conference number: 39 https://dccg.upc.edu/eurocg23/ |
Conference
| Conference | The 39th European Workshop on Computational Geometry |
|---|---|
| Abbreviated title | EuroCG 2023 |
| Country/Territory | Spain |
| City | Barcelona |
| Period | 29/03/23 → 31/03/23 |
| Internet address |