Robust nonparametric data approximation of point sets via data reduction

DOI10.1007/978-3-642-35261-4_35zbMATH Open1260.68413arXiv1205.6717OpenAlexW94982151MaRDI QIDQ4909549FDOQ4909549

Authors: Stephane Durocher, Alexandre Leblanc, Jason Morrison, Matthew Skala 

Publication date: 21 March 2013

Published in: Algorithms and Computation (Search for Journal in Brave)

Abstract: In this paper we present a novel non-parametric method of simplifying piecewise linear curves and we apply this method as a statistical approximation of structure within sequential data in the plane. We consider the problem of minimizing the average length of sequences of consecutive input points that lie on any one side of the simplified curve. 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 an ordered subset $QsubsetP$ (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}logn)$ when $P$ is monotonic and $O(n^{2}lo{g}^{2}n)$ when $P$ is an arbitrary simple polyline. Finally, we examine the application of our algorithms iteratively in a bootstrapping technique to define a smooth robust non-parametric approximation of the original sequence.

Full work available at URL: https://arxiv.org/abs/1205.6717

Recommendations

• Robust nonparametric simplification of polygonal chains
• scientific article; zbMATH DE number 1070447
• scientific article; zbMATH DE number 1947379
• Near-linear time approximation algorithms for curve simplification
• A data reduction algorithm for planar curves

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cited In (4)

• Robust nonparametric simplification of polygonal chains
• Robust nonparametric estimation of the intensity function of point data
• Improved points approximation algorithms based on simplicial thickness data structures
• Data point selection for piecewise trilinear approximation

This page was built for publication: Robust nonparametric data approximation of point sets via data reduction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4909549)