text: Chains are vector-valued signals sampling a curve. They are important to motion signal processing and to many scientific applications including location sensors. We propose a novel measure of smoothness for chains curves by generalizing the scalar-valued concept of monotonicity. Monotonicity can be defined by the connectedness of the inverse image of balls. This definition is coordinate-invariant and can be computed efficiently over chains. Monotone curves can be discontinuous, but continuous monotone curves are differentiable a.e. Over chains, a simple sphere-preserving filter shown to never decrease the degree of monotonicity. It outperforms moving average filters over a synthetic data set. Applications include Time Series Segmentation, chain reconstruction from unordered data points, Optical Character Recognition, and Pattern Matching.
  @cite_10: Abstract Given a set of points S = ( x 1 , y 1 ), ( x 2 , y 2 ), …, ( x N , y N ) in R 2 with x 1 x 2 x N , we want to construct a polygonal (i.e., continuous, piecewise linear) function f with a small number of corners (i.e., nondifferentiable points) which fits S well. To measure the quality of f in this regard, we employ two criteria: 1. (i) the number of corners in the graph of f , and 2. (ii) max 1≤i≤N ¦y i − f(x i )¦ (the Chebyshev error of the fit). We give efficient algorithms to construct a polygonal function f that minimizes (i) (resp. (ii)) under a maximum allowable value of (ii) (resp. (i)), whether or not the comers of f are constrained to be in the set S . A key tool used in designing these algorithms is a linear time algorithm to find the visibility polygon from an edge in a monotone polygon. A variation of one of these algorithms solves the following computational geometry problem in optimal O ( N ) time: Given N vertical segments in the plane, no two with the same abscissa, find a monotone polygonal curve with the least number of corners which intersects all the segments.
  @cite_14: 
  @cite_4: We consider the problem of approximating a polygonal curve P under a given error criterion by another polygonal curve P? whose vertices are a subset of the vertices of P. The goal is to minimize the number of vertices of P? while ensuring that the error between P? and P is below a certain threshold. We consider two fundamentally different error measures -- Hausdorff and Frechet error measures. For both error criteria, we present near-linear time approximation algorithms that, given a parameter ? > 0, compute a simplified polygonal curve P? whose error is less than ? and size at most the size of an optimal simplified polygonal curve with error ? 2. We consider monotone curves in the case of Hausdorff error measure and arbitrary curves for the Frechet error measure. We present experimental results demonstrating that our algorithms are simple and fast, and produce close to optimal simplifications in practice.
summary: @cite_4 @cite_14 @cite_10 , the authors chose to define monotonicity for curves or chains with an arbitrary direction vector: a curve is monotone if its projection on a line is does not backtrack. While this is a sensible choice given the lack of definition elsewhere, we argue that not all applications support an arbitrary direction that can be used to define monotonicity.