Technical Reports

The ICICS/CS Reading Room

UBC CS TR-92-05 Summary

Approximating Polygons and Subdivisions with Minimum-Link Paths, March 1992 Leonidas J. Guibas, John E. Hershberger, Joseph S. B. Mitchell and Jack Scott Snoeyink, 27 pages

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

If you have any questions or comments regarding this page please send mail to