Skip to main content
eScholarship
Open Access Publications from the University of California

Faster circle packing with application to nonobtuse triangulation

  • Author(s): Eppstein, David
  • et al.
Abstract

We show how to pack a non-simple polygon with O(n) tangent circles, so that each remaining region is adjacent to at most four circles, in total time O(n log n). This improves a previous O(n log^2 n) bound. As a consequence, we can triangulate the polygon with right and acute triangles in the same bounds.

Main Content
Current View