Простір, Заповнений Лінією Пеано: Одна Вимірна Лінія, Що Покриває Кожну Точку Квадрата

Заложення кривої, що зруйнувала XIX-вічне припущення

У 1890 році Джузеппе Пеано приголомшив математиків, побудувавши безперервну криву, яка проходить через кожну точку заповненого квадрата — одновимірний об’єкт, параметризований одним дійсним змінною t, з діапазоном, що охоплює справді двовимірну площу. Перед побудовою Пеано більшість математиків вважали, що безперервна крива просто не може мати позитивної площі; вимірювання здавалося очевидно інваріантною, інтуїтивно зрозумілою властивістю. Крива Пеано, а також краще відома 1891 року версія Давида Гільберта, показала, що лише безперервність дозволяє набагато дивніші явища, ніж здавалося на перший погляд.

Початковий правило 3x3 бустрофедону

Пеано's оригінальна конструкція розділяє одиничний квадрат на сітку 3x3, що складається з дев’яти підквадратів, і відвідує їх у бустрофедонічному порядку — зліва направо по нижньому рядку, потім справа наліво по середньому рядку, а потім знову зліва направо по верхньому рядку – щоб сусідні підквадрати завжди були суміжними, зберігаючи шлях безперервним. Кожен із цих дев’яти підквадратів потім рекурсивно ділиться та відстежується таким же чином, чергуючи орієнтацію переходу (іноді перевернуту, іноді відображену), щоб кінцеві точки кривої завжди з'єднувалися плавно з сусідами по всьому рекурсивному структурному блоку.

function peano(x, y, size, level, flip) {
  if (level === 0) { drawTo(x + size/2, y + size/2); return; }
  const s = size / 3;
  const order = flip ? [2,1,0] : [0,1,2];   // boustrophedon row order, alternated
  for (const row of order) {
    const colOrder = (row % 2 === 0) ? [0,1,2] : [2,1,0];
    for (const col of colOrder)
      peano(x + col*s, y + row*s, s, level - 1, !flip);
  }
}

Заполнение пространства без пересечения себя

На каждом уровне рекурсии количество посещенных подквадратов равно 9^уровню, и по мере увеличения уровня путь кривой проходит произвольно близко к каждой точке квадрата. В строгом математическом пределе (бесконечная рекурсия) образ кривой действительно равен всему заполненному квадрату — кривая топологической размерности 1, чья мера Лебега равна полной площади 2D, то есть множество с гауссовской размерностью точно 2. Это не противоречит тому, что кривая Пиано является непрерывной: непрерывность лишь гарантирует, что близлежащие значения параметра t отображаются в близлежащие точки, а не то, что кривую нельзя заполнить пространством; топологическая размерность домена (интервал, размерности 1) против измерения диапазона (всей квадрата), которое интуитивно — и ошибочно — предполагали должны совпадать.

Peаno проти Хільберта проти Z-послідовності: яку криву просторового заповнення використовувати?

Крива Пеано оригінально використовує трикутне поділу з основою 3 (сітки 3x3); крива Хільберта 1891 року використовує поділ з основою 2 (сітки 2x2) і стала набагато поширенішою в обчисленнях, оскільки локальність кривої Хільберта — точки, близькі одна до одної вздовж 1D параметризації, залишаються близькими у 2D просторі, і навпаки — помітно краща, ніж крива Пеано або навіть простіша крива Z-послідовності (Мортона), яка також ділиться на чверті в фіксному кутовому порядку, що призводить до випадкових великих стрибків між послідовними клітинками. Ця властивість локальності пояснює, чому порядок кривої Хільберта з'являється в реальних системах: просторові індекси бази даних, які хочуть діапазонних запитів, що торкаються небагатьох сторінок диску, алгоритми обробки зображень, які хочуть кеш-дружній перехід пікселів, і алгоритми дедування помилок, які хочуть залишатися просторово локальними. Крива Пеано, будучи першою за часом, менше використовується на практиці, але є безпосереднім предком всієї родини.

Заповнені криві просторового переміщення як метод зменшення розмірності

Оскільки заповнена крива простору дає безперервне (хоч і не гладке та не єдине-до-одного — точки можуть відвідуватися більше одного разу) відображення з 1D інтервалу на 2D (або вищомірний) простір, вона надає реальний спосіб перетворити багатовимірні дані в послідовність, що складається з одного елементу, зберігаючи при цьому концепцію «близькості». Це використовується за межами чистого розваги: алгоритми балансування навантаження, які розділяють 2D або 3D симуляційний простір між процесорами, часто йдуть по кривій Гільберта, щоб призначити безперервні відрізки кривої кожному процесору, гарантуючи, що регіон кожного процесора залишається просторово компактним, що мінімізує необхідну комунікацію між процесорами на межах частин.

Зауваження щодо поняття "виміру" в собі

Крижа Пеано є частиною того, чому математики зрештою потребували кількох більш точних визначень виміру — топологічний вимір (який залишається рівним 1 для будь-якої кривої, незалежно від того, чи заповнює простір або ні, оскільки локально вона все ще виглядає як лінія) проти Хаусдорфового або фрактального виміру (який вимірює, як масштабується "розмір" множини під час збільшення та дає зображенню кривої Пеано розмір 2, що відповідає площі, яку вона заповнює). Таке ж розрізнення, застосоване до множин з виміром строго між цілими числами, визначає такі відомі фрактали, як килим Серпінського або крива Дракона, їх нецілісний вимір.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Peano Space-Filling Curve і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.