Что такое кривые, заполняющие пространство
Линия одномерна, а квадрат двумерен, поэтому кажется очевидным, что линия никогда не сможет покрыть квадрат. В 1890 году Джузеппе Пеано показал, что сможет: существует непрерывная кривая, проходящая через каждую точку квадрата. Это открытие заставило математиков заново задуматься о том, что такое кривая и что такое размерность, а столетие спустя те же кривые поддерживают порядок в данных карт и изображений внутри компьютеров.
Столько же точек, сколько в квадрате
В 1877 году Георг Кантор доказал, что в отрезке ровно столько же точек, сколько в квадрате: каждой точке квадрата можно поставить в пару её собственную точку линии. Он написал Рихарду Дедекинду: «Я вижу это, но не верю». Однако соответствие Кантора беспорядочно скачет; оно разрывает линию в пыль. Открытым оставался вопрос, может ли линия покрыть квадрат, не разрываясь, то есть непрерывно.
Кривая Пеано
В 1890 году итальянский математик Джузеппе Пеано дал ответ: да. Он описал — одними формулами, без единого рисунка — непрерывную кривую, проходящую через каждую точку единичного квадрата. Его построение делит квадрат на 9 меньших квадратов, проходит по ним S-образными изгибами и повторяет это внутри каждого из них, снова и снова.
Рисунок Гильберта
Год спустя Давид Гильберт опубликовал более простой вариант — с рисунком, который сделал идею наглядной. Разделите квадрат на 4 части и соедините их центры одной изогнутой линией. Затем разделите каждый маленький квадрат на 4 и сделайте то же самое, поворачивая маленькие копии так, чтобы линия переходила из одной в следующую. Кривая уровня n посещает 4ⁿ клеток; квадрат же заполняет предел всех уровней. В 1900 году Элиаким Гастингс Мур предложил вариант, который заканчивается там же, где начинается, — замкнутую петлю.
Почему работает предел
Проследите за одной точкой линии — скажем, той, что лежит на трети пути. На уровне 1 она находится в одной из 4 клеток. На каждом следующем уровне она сдвигается, но остаётся внутри этой клетки, затем внутри её четверти и так далее: внутри клетки, сторона которой каждый раз уменьшается вдвое. Поэтому её положение стабилизируется, и то же верно для каждой точки линии. Предел — непрерывная кривая. А поскольку каждый уровень посещает каждую клетку всё более мелкой сетки, предельная кривая подходит сколь угодно близко к каждой точке квадрата и, будучи непрерывной, достигает её.
Взаимно однозначно не получится
Кривой, заполняющей пространство, приходится платить свою цену. В 1879 году Ойген Нетто доказал, что линию нельзя отобразить на квадрат одновременно непрерывно и взаимно однозначно. Значит, кривая должна проходить через некоторые точки больше одного раза; кривая Гильберта касается некоторых точек до четырёх раз. К тому же она нигде не гладкая: ни в одной точке у неё нет касательной.
Длина и размерность
Уровень n кривой Гильберта в 2ⁿ − 2⁻ⁿ раз длиннее стороны квадрата — примерно вдвое длиннее предыдущего уровня. Длина растёт неограниченно, и всё же кривая никогда не покидает квадрат. Кривая, составленная из 4 своих копий вдвое меньшего размера, имеет размерность log 4 / log 2 = 2 — размерность квадрата, который она заполняет. У кривой Пеано 9 копий втрое меньшего размера: тоже log 9 / log 3 = 2.
Соседи остаются рядом
У кривой Гильберта есть свойство, которое делает её полезной: точки, близкие на линии, оказываются близкими и в квадрате. Обратное не может быть верно всегда: две соседние клетки могут быть далеко друг от друга на линии. Компьютеры используют эту кривую, чтобы хранить двумерные данные — тайлы карт, пиксели или места на земном шаре — в одномерном порядке, при котором большинство соседей остаются рядом. Z-порядок, описанный Гаем Мортоном в IBM в 1966 году, решает ту же задачу чередованием битов двух координат. Он вычисляется быстрее, но держит соседей рядом хуже, потому что делает скачки.
Flowsnake Госпера и стреловидная кривая Серпинского
Не каждая кривая, заполняющая пространство, заполняет квадрат. Кривая Билла Госпера 1973 года, известная как flowsnake с тех пор, как в 1976 году о ней написал Мартин Гарднер, идёт по сетке из треугольников и ставит семь отрезков на место каждого. Она заполняет остров Госпера — фигуру с фрактальной береговой линией, семь копий которой складываются в такую же фигуру побольше. Стреловидная кривая Вацлава Серпинского на первый взгляд похожа, но в ней на каждый отрезок приходится только три части вдвое меньшего размера, и потому она ничего не заполняет: она вычерчивает треугольник Серпинского с размерностью log 3 / log 2 ≈ 1,585.
Исследуйте сами
Откройте проводник по кривым, заполняющим пространство, и нажмите «Пуск», чтобы увидеть, как перо рисует каждый уровень кривой Гильберта от начала до конца. Переключитесь на S-образные изгибы Пеано, замкнутую петлю Мура, скачущий Z-порядок, flowsnake Госпера и стреловидную кривую. Поставьте перо в любое место кривой или числовой прямой под рисунком, чтобы увидеть, какой шаг попадает в какую клетку, и включите «Показывать предыдущий уровень», чтобы увидеть, как каждый шаг превращается в целый изгиб.
Часто задаваемые вопросы
Кто открыл первую кривую, заполняющую пространство?
Джузеппе Пеано, в 1890 году. Поэтому кривые, заполняющие пространство, называют также кривыми Пеано. Кривая Давида Гильберта 1891 года известна лучше всех, потому что Гильберт первым нарисовал это построение.
Является ли кривая, заполняющая пространство, фракталом?
Она построена как фрактал — из уменьшенных копий самой себя. Но её фрактальная размерность равна 2, целому числу, потому что готовая кривая покрывает площадь. Стреловидная кривая Серпинского с размерностью около 1,585 — фрактал в обычном смысле.
Какова длина кривой Гильберта?
Уровень n в 2ⁿ − 2⁻ⁿ раз длиннее стороны квадрата: в 1,5 раза на уровне 1, в 15,94 раза на уровне 4 и почти в 256 раз на уровне 8. Предельная кривая бесконечно длинна.
Сколько уровней может нарисовать проводник?
До 8 уровней для кривой Гильберта, кривой Мура и Z-порядка, что даёт сетку из 256 на 256 клеток; 5 для кривой Пеано (243 на 243 клетки) и кривой Госпера (16 807 отрезков); и 10 для стреловидной кривой Серпинского (59 049 отрезков).
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Открыть проводник по кривым, заполняющим пространство