?

Log in

No account? Create an account

Previous Entry | Next Entry

Кривые Гильберта

На рисунках — кривые Гильберта порядка с 4 по 7. Каждая кривая — как будто нитка, аккуратно уложенная в единичном квадрате, то есть квадрате со стороной, равной единице.

Как «устроены» эти кривые, и чем замечательны?

Сначала разберемся, как построить такую кривую. Возьмем квадрат со стороной ½, уберем одну из его сторон, и поместим его точно в середину единичного квадрата, вот так:

Получилась Гильбертова кривая порядка 1. Теперь уменьшим ее ровно вдвое, и сделаем с нее 4 копии. Две передвинем, а две другие тоже передвинем и еще повернем на четверть оборота в противоположные стороны. Соединим концы линий тремя одинаковыми отрезками, длиной равной стороне нового, уменьшенного квадрата. На рисунке каждая копия окрашена своим цветом, а соединительные отрезки черные.

У нас получилась кривая порядка 2. Теперь повторим нашу процедуру, но уже с получившейся ломаной линией: уменьшим вдвое, сделаем четыре копии, две из которых повернуты, и вновь соединим отрезками, которые тоже укоротим вдвое:

Повторять этот алгоритм можно до бесконечности. Вот следующие четыре шага, с кривыми порядка от 4 до 7 включительно:

Кривая Гильберта знаменита тем, что, если повторить нашу процедуру бесконечное число раз, то она заполнит собой весь квадрат без промежутков: через любую точку внутри или на границе квадрата она будет проходить по крайней мере единожды! До работы Гильберта математики предполагали, что сделать это невозможно[2].

Разумеется, повторить алгоритм бесконечное число раз нельзя; говоря о бесконечностях, следует оперировать пределами, ε-окрестностями и прочими понятиями матанализа.

Доказательство[3] существования предельной кривой основывается на таком рассуждении (приведу здесь только основную наглядную идею). Расположим кривую порядка 2 (красная линия, средней толщины) поверх кривой порядка 1 (синяя, самая толстая линия). Видно, что первая как бы «обвивает» последнюю. Еще более это отношение заметно между кривыми порядка 2 и 3 (тонкая зеленая линия).

Возьмем кусочек бесконечно растяжимой резинки и нанесем на нее шкалу от 0 до 1. Разные участки резинки могут быть растянуты по-разному. Натянем ее по форме кривой первого порядка так, что концы будут соответствовать 0 и 1, а середины каждой из трех сторон — 1/4, 2/4 и 3/4 соответственно. Теперь возьмем еще одну такую же резинку, и растянем ее вдоль кривой второго порядка. Концы кривой опять прикрепим в точках 0 и 1, а к серединам каждого из 15 отрезков, составляющих кривую, прикрепим точки начиная с 1/16 и заканчивая 15/16. Легко видеть, что расстояние между соответствующими одному и тому же числу точках на двух резинках не превышает диагонали квадрата со стороной, равной длине каждого из отрезков кривой второго порядка.

Поскольку с каждой итерацией сторона будет уменьшаться вдвое, то установленное нами «отклонение» одной резинки от другой с увеличением номера итерации будет стремиться к нулю вместе с длиной отрезков, из которых кривая составлена. Обратите внимание, что каждая из резинок — это функция: если число на резинке оказалось в какой-то точке квадрата, то функция как раз и отображает это значение на точку в квадрате.

По теореме Коши, поскольку разница между любыми двумя функциями стремится к нулю (транзитивность тут доказывается разложением в геометрический ряд, см. [3]), то и предельная функция существует и непрерывна. Интуитивно это понятно из рисунка: с каждой итерацией расстояние между кривыми порядка n+1 и n, первой «обвивающей» последнюю, делается все меньше и меньше.

Далее следует доказать, что кривая проходит через любую точку квадрата. Рассуждение здесь такое. Кривая порядка 1 проходит на расстоянии не далее 1/4 от любой точки внутри квадрата. Поэтому любая из четырех ее уменьшенных копий в кривой второго порядка оказывается не далее 1/8 от любой точки каждой из четырех четвертей квадрата, а, значит, любая точка всего квадрата удалена от кривой не более, чем на 1/8. Кривая третьего порядка лежит не далее, чем в 1/16 от любой точки в квадрате, и так далее. Таким образом, в предельном случае кривая будет проходить в ε-окрестности любой точки внутри квадрата. Тогда для некоей последовательности аргументов функции, последовательность соответствующих значений непременно сойдется в данную точку; иными словами, кривая проходит через все точки квадрата. Строго можно доказать, что кривая не только проходит через все точки квадрата, но и «не влезает» в квадрат — через почти все некоторые точки она проходит более одного раза! (Это следует, например, из неизоморфности отрезка [0;1] единичному квадрату: на отрезке удаление почти любой точки рассекает его на два несвязных подмножества, а в квадрате такой точки нет) [Возможно, это ошибка. Ссылка в обсуждение — прочитайте!].

Интересен вопрос, можно ли говорить о фрактальности этой кривой. С одной стороны, кривая, безусловно, самоподобна, за исключением соединительных отрезков, в силу построения. С другой стороны, под Мандельбротово определение фрактала она не попадает[4]: поскольку кривая заполняет весь квадрат, то ее Хаусдорфова размерность совпадает с топологической, и равна 2. Так что ответ зависит от решения о том, что следует считать фракталом. В некотором смысле, кривая Гильберта находится на границе между фрактальными и не фрактальными объектами.

Алгоритмически Гильбертова кривая удобно строится с помощью переписывающей символьной системы Линденмайера (L-System)[5], конечный результат преобразования в которой интерпретируется как «черепашья» графика[6]. Если интересно, то об этом можно будет поговорить отдельно. А здесь пока приведу только код для Mathematica 6.0, с помощью которого были построены все иллюстрации:

LIterate[omega_, rules_, n_] := 
  Nest[StringReplace[#, rules]&, omega, n];

QuadPart[list_] :=
  With[{m = Length[list]/4},
   Flatten[
     Partition[#, m, m-1, {1,2}, {}]& /@ 
      Partition[list, m+1, m, {1,m}, {}], 1] /; IntegerQ[m] && m > 1];

HilbertCurve[r_, s_] :=
  Module[{
      omega = "L",
      rules = {"L" -> "+RF-LFL-FR+", "R" -> "-LF+RFR+FL-"},
      colority = 0.8,
      ttl, pts},
     
    ttl[{p_, d_}, "F"] := {p + d, d};
    ttl[{p_, d_}, "+"] := {p,   I*d};
    ttl[{p_, d_}, "-"] := {p,  -I*d};
    ttl[pd_, _] := pd;
   
    pts = 2^(s-r) * {Re[#], Im[#]}& /@ First /@ Split[
       First /@ FoldList[ttl, {0,1}, Characters @ LIterate["L", rules, r]]];
      
    Graphics[Style[{
       Thickness[1.5^(-r-8)],
       If[r > 1,
        MapThread[
         {#1, Line @ #2} &, {
          Riffle[Hue[#, 1, colority]& /@ (0.25 * Range[0, 3]), Black],
          QuadPart[pts]}],
        Line[pts]]}, Antialiasing -> False], {
      ImageSize -> 2^s * {1,1},
      ImagePadding -> None,
      PlotRangePadding -> 2^(s-r-1) * {1,1} }]
  ];

Table[HilbertCurve[i, 8], {i, 1, 7}]

Полезная литература

1. M. Gardner, Penrose Tiles to Trapdoor Ciphers, W. H. Freeman and Co. : NY, 1989.

2. E. W. Weisstein. Plane-Filling Function in MathWorld—A Wolfram Web Resource.

3. A. Bogomolny, Plane Filling Curves in Interactive Mathematics Miscellany and Puzzles.

4. B. Mandelbrot. The Fractal Geometry of Nature, W. H. Freeman and Co. : NY, 1982. Русское изд.: Б. Мандельброт. Фрактальная геометрия природы. Институт компьютерных исследований : M., 2002.

5. L-system in Wikipedia.

6. Web Turtle by Bill Kendrick.

Comments

( 25 comments — Leave a comment )
rwalk
Apr. 8th, 2009 12:14 pm (UTC)
Очень хорошо написано. Кстати, после нашего предыдущего разговора на фрактальные темы я придумал проект для студента - как раз про изучение хаусдорфовой размерности мер, возникающих из L-системы, порождающей кривую Гильберта (в этом смысле она и является фрактальной).
fregimus
Apr. 8th, 2009 12:33 pm (UTC)
Спасибо. Рад, что помог Вам.
rwalk
Apr. 8th, 2009 01:14 pm (UTC)
А вот насчет того, что кривая проходит через почти все точки квадрата больше одного раза, Вы не правы. Через почти все точки квадрата она ровно один раз проходит. Аргумент о негомеоморфности отрезка и квадрата тут не вполне по существу.
fregimus
Apr. 8th, 2009 01:20 pm (UTC)
Да, пожалуй. Завтра подумаю. У меня уже 6 утра, а я еще не — голова уже не варит.
fregimus
Apr. 9th, 2009 03:12 am (UTC)
Так и не понял, в чем моя ошибка. Можно ли вот так рассуждать, чтобы доказать более слабое утверждение о том, что кривая «переполняет» квадрат? Я повторю свои рассуждения, а Вы скажите, пожалуйста, где она вкралась.

1. Отображение квадрата на отрезок [0;1] не изморфно.
2. Отображение отрезка [0;1] на предельную кривую Гильберта (ПКГ) изоморфно.
3. Из 1 и 2, отображение квадрата на ПКГ не изоморфно.
4. Каждой точке квадрата соответствует хотя бы одна точка на ПКГ (доказано в тексте).
5. Из 3 и 4, по крайней мере одной точке квадрата соответствует более одной точки на ПКГ, QED.

Отсюда получается, что такая точка существует — конечно, не то, что это почти все точки. Или я Вас неправильно понял, что аргумент о негоеоморфности не доказывает только именно части о «почти всех» точках?

Edited at 2009-04-09 03:17 am (UTC)
rwalk
Apr. 9th, 2009 07:02 am (UTC)
Тут есть несколько моментов, которые вызывают путаницу. Для начала, не вполне понятно, что Вы называете "изоморфизмом". Я предполагал, что это гомеоморфизм, т.е., изоморфизм в категории топологических пространств (вообще, в разговоре о топологических пространствах слово "изоморфизм" несколько режет ухо; сказать, что два линейных пространства изоморфны нормально, а вот два топологических пространства именно гомеоморфны - так уж исторически сложилось). Действительно, отрезок и квадрат негомеоморфны, поскольку, как Вы справедливо пишете, удаление "внутренней" точки разделяет отрезок на две компоненты связности (но сами-то эти компоненты связны - тут у Вас неточность), а в квадрате таких точек нет.

Если внимательно посмотреть на это рассуждение, то в нем используется то обстоятельство, что непрерывный образ связного топологического пространства тоже связен. Поскольку в нашем случае связным является проколотый квадрат, то тем самым надо использовать непрерывность не исходного отображения отрезка в квадрат, а обратного отображения (непрерывность которого априори не очевидна).

Таким образом, строгое доказательство того, что существуют точки, через которые кривая Гильберта проходит несколько раз, выглядит так. Сама кривая - это непрерывное отображение f:I->Q (I - замкнутый отрезок, Q - квадрат, включая границу). Если f взаимно однозначно, то обратное отображение тоже непрерывно, и тем самым f - гомеоморфизм (это классическая теорема из топологии: непрерывное взаимно-однозначное отображение компакта на хаусдорфово пространство является гомеоморфизмом). Только теперь можно применить соображение о несвязности/связности проколотых пространств.

Собственно, сами кратные точки легко описать. Разобьем исходный квадрат на 4 равных квадратика первого уровня, каждый из них на 4 квадратика 2 уровня и т.д. (квадратики первого уровня у Вас раскрашены на картинках). Тогда кратные точки - это в точности границы квадратиков, а кратность - это максимальное количество (замкнутых) квадратиков одного уровня, которым заданная точка может принадлежать, т.е., она принимает значения 1 (множество меры 1), 2 (несчетное множество меры 0), 4 (счетное множество).
fregimus
Apr. 10th, 2009 09:03 pm (UTC)
Спасибо! Да, у меня очень «сырое» получилось рассуждение, поэтому неточно все. А Вы хорошо очень все расписали.
kcmamu
Apr. 8th, 2009 12:29 pm (UTC)
Откуда взялось название "типографическая система Линденмайера"?

Касательно фрактальной природы: кривые (x(t), y(t)) можно рассматривать и в трехмерном пространстве (x, y, t).
fregimus
Apr. 8th, 2009 12:40 pm (UTC)
Слово «типографическая»? Из английского typographic. Идея такой системы в том, что символами оперируют по правилам, но не придавая им никакого смысла, совершенно формальным образом. В переводе GEB я видел «типографская», но это слово означает «относящийся к типографии», здесь оно явно не подходит. «Символьная» тоже занята. А как-то выкручиваться надо. Слово typographic в английской голове вызывает ассоциации с type и graphic — так что и мой вариант не лучший. Посоветуете лучший?

Вариации на тему кривых Гильберта возможны в метризуемом пространстве любой конечной размерности, не только трех.
kcmamu
Apr. 8th, 2009 12:54 pm (UTC)
Что-то не могу найти ни единого употребления этого английского слова применительно к L-системам. Или это был случайный одноразовый эпитет, а не термин? Тогда можно сказать "перепечатывающий".
fregimus
Apr. 8th, 2009 01:06 pm (UTC)
Не думаю, что одноразовый. Хофштадтер таким термином пользуется без объяснений, хотя и говоря не об L-системах, а о формальных системах вообще. В википедии “parallel rewriting system”. Думаю, можно сказать «формальная символьная» система. Годится?
kcmamu
Apr. 8th, 2009 01:19 pm (UTC)
Вроде да.
Вот "rewriting system" давно традиционно переводят как "переписывающая система".

Edited at 2009-04-08 01:20 pm (UTC)
fregimus
Apr. 8th, 2009 01:21 pm (UTC)
Ага, спасибо. Так и сделаю.
bvn_mai
Apr. 8th, 2009 04:43 pm (UTC)
:)
fregimus
Apr. 9th, 2009 03:15 am (UTC)
Пожалуйста.
fat_crocodile
Apr. 8th, 2009 05:47 pm (UTC)
О, я как раз сегодня начал в эту сторону расширять сознание.
Посоветуете что-нибудь конкретное почитать, или всё примерно одинаково полезно?

На счёт "более одного раза" я не понял, по построению кривая вообще без самопересечений, вроде.
fregimus
Apr. 9th, 2009 03:16 am (UTC)
По построению — да, без самопересечений, конечно. Но в пределе с самокасаниями.

По поводу расширения сознания — у Гарднера очень популярно (хотите — в файле пришлю, кажется, где-то у меня была, по-английски). Ну, а Мандельброт — вообще душка, одно удовольствие читать!
fat_crocodile
Apr. 10th, 2009 03:14 pm (UTC)
Спасибо за рекомендации.

Если найдёте Гарднера и отправите его на sergho-собака-gmail-com, буду вам премного благодарен.

А за Мандельбротом, видимо, стоит сходить в библиотеку. Лет шесть повода не находил :)
fat_crocodile
Apr. 10th, 2009 03:51 pm (UTC)
Ну вот, нашёл в сети. И когда я теперь в библиотеку пойду?
fregimus
Apr. 10th, 2009 09:18 pm (UTC)
Вот обе в файлах нашлись:

Penrose Tiles to Trapdoor Ciphers - M. Gardner (1989)

The Fractal Geometry of Nature - B. Mandelbrot (Freeman, 1983)


Edited at 2009-04-10 09:21 pm (UTC)
fe_b
Apr. 9th, 2009 08:09 am (UTC)
Эта кривая - хорошая метафора для творения мира.
По такому пути внимание/воля Бога пробегает по всему космосу.
Разные приближения этой кривой соответствуют разным масштабам пространства и времени.
a_konst
May. 13th, 2009 08:53 am (UTC)
Странно, меня всегда учили, что это назвается "кривая Пеано".
fregimus
May. 13th, 2009 07:25 pm (UTC)
Есть кривые Пеано в частности (S-образная кривая 1 порядка), а, кроме того, кривыми Пеано называют кривые, заполняющие плоскость, вообще: Because Giuseppe Peano (1858–1932) was the first to discover one, space-filling curves in the 2-dimensional plane are commonly called Peano curves.

В разных странах названия могут быть разные, конечно. Это как теорема Найквиста (Котельникова, Шеннона, и т. д.).
lastcomm
Apr. 6th, 2010 06:04 pm (UTC)
Кривая Г. позволяет параметризовать непрерывную функцию двух (n) переменных в непрерывную же функцию одной переменной. Я очень обрадовался (я предпочитаю находить одномерные минимумы, корни, интегралы и т.п.), но вскоре понял, что результат будет нигде не дифференцируемый. Как курс доллара. В связи с этим у меня вопрос: а есть "математический анализ" для нигденедифференцируемых функций? Хоть что-нибудь с ними можно сделать, кроме как смотреть на них? Где про них почитать?
fregimus
Apr. 6th, 2010 11:28 pm (UTC)
Не припоминаю, чтобы было такое. Кажется, только смотреть. Такие кривые — объект изучения фрактальной геометрии, но не могу представить, как бы они могли в анализе применяться.

Спросите в ru_math — я наверняка не знаю.
( 25 comments — Leave a comment )