Geometry & Intervals: The Architecture of Space

The Curse of Dimensionality

Sorting numbers is easy. Is 5 bigger than 3? Yes. But sorting space is hard. Is (5, 3) bigger than (4, 8)? It depends.

When data has multiple dimensions (Latitude/Longitude, Start Time/End Time, X/Y/Z), a simple list is no longer enough. If you want to find “the nearest gas station” or “all meetings that overlap with 2 PM,” you cannot simply scan a sorted array.

This section is about Spatial Indexing. It is the art of partitioning space (and time) into manageable hierarchies, allowing us to query infinite planes with finite speed.

The Strategy of Partition

In this section, we move from 1D lines to N-D worlds:

The Three Laws of Space

1. Hierarchy: To search space efficiently, you must group empty space together. If a huge box is empty, you don’t need to look inside it.
2. Overlap: Unlike sorting numbers, spatial objects can overlap. A robust algorithm must handle the ambiguity of “being in two places at once.”
3. The Curse: As dimensions increase, distance becomes meaningless. In 1000-dimensional space, everything is “far” from everything else. Standard spatial trees fail here (approximate methods are needed).

Summary

In this section, we will see how computer graphics, databases, and GPS systems solve the problem of “Where.” We will learn that organizing space is surprisingly similar to organizing a messy closet: putting things in boxes, and putting those boxes in bigger boxes.

Let’s start with the simplest dimension: Time (1D Intervals).