Optimal simplification of polygonal chains for subpixel-accurate rendering

For a given polygonal chain, we study the min-# problem, which consists of finding an approximate and ordered subchain with a minimum number of vertices under a given approximation criterion. We propose the first near-linear time algorithm for the min-# problem that ensures optimality in the number of vertices and that retains the shape of the input polygonal chain at the same time. Previous algorithms with near-linear time performance produced geometrical inconsistencies and former methods used to preserve the features of the original chain required a quadratic time complexity. When we set the approximation error equal to the pixel pitch, our simplification criterion guarantees that the rendering of the simplification lies at most half a pixel away from the original chain, contrary to other methods that do not offer a direct control over the rendering. Thus, we avoid producing visible topological inconsistencies. Moreover, our method is based on basic data structures, which leads to a simple and efficient implementation.