# David Eppstein - Publications

##

**Faster circle packing with application to nonobtuse triangulation**.

D. Eppstein.

Tech. Rep. 94-33, ICS, UCI 1994.

*Int. J. Comp. Geom. & Appl.* 7 (5): 485–491, 1997.
Speeds up a triangulation algorithm of Bern et al.
["Linear-Size
Nonobtuse Triangulation of Polygons"] by finding a
collection of disjoint circles
which connect up the holes in a non-simple polygon.
The method is to use a
minimum spanning tree to find a collection of
overlapping circles, then shrink them one by one to reduce the number of
overlaps, using Sleator and
Tarjan's dynamic tree data structure to keep track of the
connectivity of the shrunken circles.

Publications –
David Eppstein –
Theory Group –
Inf. & Comp. Sci. –
UC Irvine

Semi-automatically filtered
from a common source file.