Computing Minimum Complexity 1D Curve Simplifications under the Fréchet Distance

Onderzoeksoutput: Bijdrage aan congresPaperAcademic

133 Downloads (Pure)

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.
Originele taal-2Engels
Pagina's62:1-62:6
Aantal pagina's6
StatusGepubliceerd - 29 mrt. 2023
EvenementThe 39th European Workshop on Computational Geometry - Universitat Politècnica de Catalunya, Barcelona, Spanje
Duur: 29 mrt. 202331 mrt. 2023
Congresnummer: 39
https://dccg.upc.edu/eurocg23/

Congres

CongresThe 39th European Workshop on Computational Geometry
Verkorte titelEuroCG 2023
Land/RegioSpanje
StadBarcelona
Periode29/03/2331/03/23
Internet adres

Vingerafdruk

Duik in de onderzoeksthema's van 'Computing Minimum Complexity 1D Curve Simplifications under the Fréchet Distance'. Samen vormen ze een unieke vingerafdruk.

Citeer dit