Faster Circle Packing with Application to Nonobtuse Triangulation
David Eppstein · International Journal of Computational Geometry & Applications · 1997
We show how to pack a non-simple polygon with O(n) tangent circles, so that the union of the polygon boundary components and circles is connected, in total time O(n log n). This improves a previous O(n log 2 n) bound. By combining this with methods of Bern, Mitchell, and Ruppert we can extend this to a circle packing in which each portion of the polygon outside the circles is adjacent to at most four circles or boundary edges, and as a consequence we can triangulate the polygon with right and acute triangles, using O(n) Steiner points, again in the same O(n log n) time bound.