The Algorithm Design Manual Second Edition

Stop and Think: Bucketing Rectangles

Problem: “In my graphics work I need to solve the following problem. Given an

arbitrary set of rectangles in the plane, how can I distribute them into a minimum

number of buckets such that no subset of rectangles in any given bucket inter-

sects another? In other words, there can not be any overlapping area between two

rectangles in the same bucket.”

Solution: We formulate a graph where each vertex is a rectangle, and there is an

edge if two rectangles intersect. Each bucket corresponds to an independent set of

rectangles, so there is no overlap between any two. A vertex coloring of a graph is a

partition of the vertices into independent sets, so minimizing the number of colors

is exactly what you want.