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.
