APPROXIMATING POLYGONS AND SUBDIVISIONS WITH MINIMUM-LINK PATHS
Leonidas Guibas, John E. Hershberger, Joseph S. B. Mitchell, Jack Scott Snoeyink · International Journal of Computational Geometry & Applications · 1993
We study several variations on one basic approach to the task of simplifying a plane polygon or subdivision: Fatten the given object and construct an approximation inside the fattened region. We investigate fattening by convolving the segments or vertices with disks and attempt to approximate objects with the minimum number of line segments, or with near the minimum, by using efficient greedy algorithms. We give some variants that have linear or O(n log n) algorithms approximating polygonal chains of n segments. We also show that approximating subdivisions and approximating with chains with. no self-intersections are NP-hard.