Pigeonhole distance bound from a partition
ID: pigeonhole-distance-bound-from-a-partition
Suppose a subset of a metric space is covered by sets, each of diameter at most . Assign each point to one covering set containing it, choosing a single set at shared boundaries. Among points, the pigeonhole principle puts two in a common set, and their distance is at most . The pieces need not be equal or congruent. This freedom permits better distance bounds than dividing a region only into equal rectangles.
New to topics? Read the docs here!