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.

Fano Experimental Web Server, D. Eppstein, School of Information & Computer Science, UC Irvine
Made on a Mac Valid XHTML 1.0!