Coordinate compression is a procedure that takes some points and reassigns their coordinates to remove "gaps". For example, if point P1 is located at x = 5, point P2 is located at x = 27, and point P3 is located at x = 65, then, after coordinate compression, P1 may be located at x = 0, P2 may be located at x = 1, and P3 may be located at x = 2. The reason we compress coordinates is to get rid of all the "empty space" between points. This makes it easier to, say, use the coordinates as indices into an array. If we used the original numbers, we'd waste a lot of entries.

Performing coordinate compression is easy. You just make a list of all the coordinates and sort them in ascending order. This gives you the rank of each coordinate. You then replace each coordinate by its rank. This takes O(N log N) time, so it's pretty efficient.

A simple problem that can be solved using coordinate compression is the problem of finding the volume of the union of N axis-aligned boxes in three dimensions (1 <= N <= 100). The coordinates can be arbitrary real numbers between 0 and 10^9.

The shape of this union can be complicated, but observe that if we compress the coordinates, then all coordinates will lie between 0 and 199, since each box has two coordinates along each dimension. In the compressed coordinate system, the unit cube [math][x, x+1] \times [y, y+1] \times [z, z+1][/math] will either be completely full or completely empty, since each box's coordinates are integers. So the idea is to compute a 200x200x200 array, in which each entry is 1 if the corresponding unit cube is full, or 0 of it's empty. To actually compute this array in linear time can be done by first forming the difference array and then integrating. After that, iterate through each filled cube, and map it back to the original coordinates, and add its volume to the total volume. The overall running time is O(N^3).

(Follow-up problem: find the surface area.)