Approximating Polygons and Subdivisions with Minimum-Link Paths

ID
TR-92-05
Authors
Leonidas J. Guibas, John E. Hershberger, Joseph S. B. Mitchell and Jack Scott Snoeyink
Publishing date
March 1992
Length
27 pages
Abstract

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 withem 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, and show that for subdivisions or chains with no self-intersections it is NP-hard to compute the best approximation.