Inproceedings,
Approximating Polygons and Subdivisions with Minimum Link Paths
Proceedings of the 2nd International Symposium on Algorithms, page 151--162. London, Springer, (1991)
Abstract
In the practical application of computers to graphics, image processing, and geographica information systems, one often wishes to replace complex geometric objects with simpler objects that capture the relevant features of the original. 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 ecient greedy algorithms. We also discuss additional topological constraints such as simplicity.
