Polygonal chain approximation: a query based approach

In this paper we present a new, query based approach for approximating polygonal chains in the plane. We give a few results based on this approach, some of more general interest, and propose a greedy heuristic to speed up the computation. Our algorithms are simple, based on standard geometric operations, and thus suitable for efficient implementation. We also show that the query based approach can be used to obtain a subquadratic time exact algorithm with infinite beam criterion and Euclidean distance metric if some condition on the input path holds. Although in a special case, this is the first subquadratic result for path approximation with Euclidean distance metric.