Mathematical Reviews 99d:52018

Faster circle packing with application to nonobtuse triangulation
David Eppstein
Int. J. Computational Geometry & Applications 7(5):485–491, Oct 1997
Mathematical Reviews 99d:52018, 1999
Reviewed by Frederic Matheus

Numerical computations regarding the discretization of Dirichlet problems in polygonal domains need to generate triangulations with right or acute angles. The author considers here a recent work of Bern, Mitchell and Ruppert which uses circle packings to generate such meshes and speed up a key step of their method in which circles are packed into a non-simply connected polygonal region to connect its boundary components. In the work of Bern et al., this step was computed in $O(n\log\sp {2}n)$ time. The new method presented here leads to an overall speedup of a logarithmic factor, which makes the whole algorithm work in total time $O(n\log n)$. This method for connecting the boundary components of a polygon relies on a combination of several known techniques such as: Voronoi diagrams, minimum spanning trees, intersection graphs, neighborhood system algorithms of Eppstein, Miller and Teng, and dynamic tree techniques of Sleator and Tarjan.