Robust Nonparametric Data Approximation of Point Sets via Data Reduction

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. 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 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) root log n) when P is monotonic and O(n(2) log(4/3) n) when P is any simple polyline.