Coordinate Compression (Reducing Large Values to Manageable Indices)

Coordinate compression (also called discretization) maps huge coordinates like 10⁹ to small ranks 0..k-1 so you can use arrays, segment trees, or sweep lines without wasting memory.

Why this shows up in the real world

GIS mapping, game collision, and competitive programming geometry problems all boil down to coordinates, ordering, and careful integer arithmetic.

Core idea (explained for students)

Collect every x (and y) that appears in points or event boundaries. Sort unique values, replace each coordinate with its index in that sorted list. After logic on ranks, map answers back if needed.

Try this in Python

def compress(vals: list[int]) -> tuple[list[int], dict[int, int]]:
    uniq = sorted(set(vals))
    rank = {v: i for i, v in enumerate(uniq)}
    return [rank[v] for v in vals], rank


xs = [1000000000, 5, 1000000000, 42]
compressed, _ = compress(xs)
print(xs, "->", compressed)

Common mistakes

• Forgetting to compress both axes in 2D problems.
• Off-by-one when values repeat (use bisect / unique sort).
• Comparing compressed indices as if they were original distances.

Key takeaways

• Always ask: “Which coordinates can actually appear in events?”
• k unique values → O(k log k) sort, then O(1) rank lookup with a hash map.