I recently came across a cool geometry problem from an old ICPC qualifier event: Ink Blots from the 2004 ACM ICPC Mid-Central North American Regional Contest. In this blog I describe a solution to the problem. In the problem, you are given a set of ink blots (the number of blots is less than 100), which are perfect, black circles on a piece of paper. You have to calculate the number of white regions created by these blots.

How do we go about counting these regions? A really stupid algorithm would be:

• Divide the paper in “very small” pixels
• Colour the pixels black or white, depending on if they’re inside a blot or not
• Do a Graph Traversal such as BFS/DFS to find the amount of connected white regions.

These pixels are only a approximation, and we could miss very small white regions or accidentally disconnect a white region in multiple regions because it’s too narrow in one place. Because the constraints on the dimensions of the circles are huge, this approach is doomed to fail or time out.

For a better algorithm, we have to make an observation: A white region is always bounded by a cycle of circle segments. (The unbounded region outside all the blots is a special case). These circle segments are connected by intersections of the circles. So we could just calculate all circle intersections first. Only some of the intersections are interesting, only those that are not covered by a blot, so we filter these out. A candidate circle segment is always between two adjacent intersections, when the intersections around a circle are polar sorted. So we can construct a graph, where the circle segments are edges and the interesting intersections are vertices. This graph will be a collection of cycles. With a simplified DFS, we can find all cycles in a graph.

Now the only trouble is that some cycles are on the outside of some blots, and don’t enclose a white region. We have to ignore these cycles. To achieve this, we check the orientation of the cycles, (clockwise or counterclockwise), and only add 1 to the answer if it’s in the correct orientation.

For the time complexity: The amount of circle intersections could be O(n^2), but finding all intersections and checking if they’re interesting can only be done in O(n^3). The graph made will have O(n^2) vertices and cycles, but it again requires a bigger complexity O(n^2 log(n)) to construct it. This is because of the polar sort of the intersections of the circles. The graph traversal and orientation checking can be done in O(n^2), thus the algorithm is O(n^3).

I made a cool visualization of my program that solves all the testcases here