Samenvatting
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.
Originele taal-2 | Engels |
---|---|
Pagina's | 62:1-62:6 |
Aantal pagina's | 6 |
Status | Gepubliceerd - 29 mrt. 2023 |
Evenement | The 39th European Workshop on Computational Geometry - Universitat Politècnica de Catalunya, Barcelona, Spanje Duur: 29 mrt. 2023 → 31 mrt. 2023 Congresnummer: 39 https://dccg.upc.edu/eurocg23/ |
Congres
Congres | The 39th European Workshop on Computational Geometry |
---|---|
Verkorte titel | EuroCG 2023 |
Land/Regio | Spanje |
Stad | Barcelona |
Periode | 29/03/23 → 31/03/23 |
Internet adres |