Robust Nonparametric Simplification of Polygonal Chains

Stephane Durocher, Alexandre Leblanc, Jason Morrison, Matthew Skala

Publikation: Artikel i tidsskrift og konference artikel i tidsskriftTidsskriftartikelForskningpeer review

Abstract

In this paper we present a novel nonparametric method for simplifying piecewise linear curves and we apply this method as a statistical approximation of structure within sequential data in the plane. Specifically, given a sequence P of n points in the plane that determine a simple polygonal chain consisting of n-1 segments, we describe algorithms for selecting a subsequence Q subset of P (including the first and last points of P) that determines a second polygonal chain to approximate P, such that the number of crossings between the two polygonal chains is maximized, and the cardinality of Q is minimized among all such maximizing subsets of P. Our algorithms have respective running times O(n(2) log n) (respectively, O(n(2) root log n))when P is monotonic and O(n(2) log(2) n) (respectively, O(n(2) log(4/3) n)) when P is any simple polygonal chain in the Real RAM model (respectively, in the Word RAM model).
OriginalsprogEngelsk
TidsskriftInternational Journal of Computational Geometry and Applications
Vol/bind23
Udgave nummer6
ISSN0218-1959
StatusUdgivet - 2014

Emneord

  • Polygonal line approximation
  • robust simplification
  • nonparametric methods

Fingeraftryk

Dyk ned i forskningsemnerne om 'Robust Nonparametric Simplification of Polygonal Chains'. Sammen danner de et unikt fingeraftryk.

Citationsformater