Кривая Пеано — функция, заполняющая пространство

Может ли линия заполнить квадрат?

Интуиция говорит нет. Линия — одномерная, квадрат — двумерный. Но в 1890 году Джузеппе Пеано построил непрерывную функцию f: [0,1] → [0,1]², образ которой — весь единичный квадрат целиком. Это разрушило привычные представления о размерности.

Как это устроено

Год спустя Гильберт предложил наглядную конструкцию: начните с S-образной кривой через 4 клетки. Разбейте каждую на 4 подклетки — уровень 2 (16 клеток). Повторите рекурсивно. На уровне 6 кривая посещает 4096 точек и квадрат визуально заполнен. Предел — непрерывная сюръекция [0,1] → [0,1]².

Свойство локальности

Точки, близкие на кривой по параметру t, оказываются близкими в 2D. На этом свойстве держатся три важные технологии:

LSH (Locality-Sensitive Hashing) — проекция многомерного вектора на кривую сохраняет близость. Схожие векторы → схожие хэши. Основа approximate nearest neighbor в векторных базах данных.

Z-order (Morton) кривые — индексирование в PostgreSQL, BigQuery, геопространственных системах. Google S2 library нумерует ячейки поверхности Земли по кривой Гильберта: запрос “найди в радиусе X” → range scan.

Vision Transformer (ViT) — порядок патчей по кривой Гильберта сохраняет пространственную близость лучше стандартного raster-scan. Соседние токены в последовательности = соседние в изображении.

Математика 1890 года — внутри Google Maps, PostgreSQL и современных трансформеров. Красивый мост между одномерным индексом и многомерной геометрией.

Какие ещё применения space-filling curves видите?

#ML #math #algorithms #deeplearning #нейросети