Robust nonparametric data approximation of point sets via data reduction

DOI10.1007/978-3-642-35261-4_35MaRDI QIDQ4909549zbMATH OpenOpenAlexFDO

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

Publication date 21 March 2013

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

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

Mathematics Subject Classification ID

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

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.

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

Cited in

(4)

• Robust nonparametric simplification of polygonal chains
• Improved points approximation algorithms based on simplicial thickness data structures
• Robust nonparametric estimation of the intensity function of point data
• 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)