Technical Reports

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.