О квадратно-линейном отношении правильных кривых Пеано

• Автор: Бауман, Константин Евгеньевич
• Шифр специальности: 01.01.04
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Москва
• Количество страниц: 72 с. : ил.

Содержание
Введение

1 Квадратно-линейное отношение кривой Пеано-Гильберта

1.1 Кривая Пеапо-Гильберта

1.2 Оценка снизу

1.3 Оценка сверху

2 Оценка снизу квадратно-линейного отношения правильных кривых Пеано

2.1 Известные оценки

2.2 Расположение концов правильных кривых Пеано

2.3 Оценка снизу для специальных кривых

2.4 Оценка снизу квадратно-линейного отношения правильных кривых Пеано

3 Рациональность квадратно-линейного отношения и расположение экстримальных точек
4 Кодирование правильных кривых Пеано
4.1 Запись второго шага с помощью кода
4.1.1 Вершинный код
4.1.2 Стыки
4.1.3 Производные стыки
4.2 Описание программы
4.2.1 Общее описание
4.2.2 Примеры запуска
5 Правильные односторонние кривые Пеано
рода
5.1 Расположение концов
5.2 Правильные односторонние кривые Пеано фрактального рода
9 с диагональным переходом
5.3 Односторонние кривые Пеано фрактального рода 9 без диагонального перехода
5.3.1 Единственность первого шага
5.3.2 Множество минимальных односторонних кривых рода
5.3.3 Квадратно - линейное отношение кривых
множества М
Список литературы
Приложение: код программы

Введение
Диссертация является исследованием в области фрактальной и комбинаторной геометрии. Основным объектом изучения являются численные фрактальные инварианты кривых Пеано, а именно квадратно- линейное отношение.
Под кривой Пеано подразумевается любое непрерывное отображение числового отрезка на плоский квадрат. Первая такая кривая была построена итальянским математиком Джузеппе Пеано в 1890 году ([7]). Через год Давид Гильберт предложил свой вариант кривой, который стал более известным благодаря симметричности и простоте построения ([8]). С тех пор свои варианты пеановских отображений строили многие математики, среди которых Лебег и Серпинский. Ганс Саган (Hans Sagan) в своей книге [3] приводит довольно подробное описание наиболее известных вариантов построения кривых Пеано.
Правильной фрактальной кривой Пеано согласно [2], называется отображение отрезка на квадрат, допускающее разбиение области определения на несколько равных отрезков (фрактальных периодов), таких что ограничение кривой на любой из ее фрактальных периодов подобно всей кривой. Количество (минимально возможное) фрактальных периодов называется фрактальным родом кривой. Фрактальный род кривой Пеано, образом которой является квадрат, сам является полным квадратом. Кривая Пеано-Гильберта является единственной (с точностью до симметрии и подобия) кривой фрактального рода 4.
Как и все фракталы, кривые Пеано активно используются в самых разных областях современной науки. В вычислительной математике они используются для численного интегрирования функций многих переменных. Они также имеют свое приложение в алгоритмах ([21], [22], [23]) и вычислительной гидродинамике ([16]).
В биологии и медицине кривые Пеано применяются для объяснения структуры головного мозга человека ([10]). Ученые из Гарвардского университета в США пришли к выводу, что ДНК заполняет каждую клетку таким образом, что ее пространственная конструкция приближается к конструкции кривой Пеано.
В работе с базами данных кривые Пеано используются для преобразования многомерных данных к одномерным ([13], [14],[20], [24], [25])
Интересное приложение кривых Пеано описано в статье [15]. В ней авторы показывают как красиво и информативно изобразить на рисунке граф с множеством связей. Для этого предлагается выделить на нем плотные множества, расположить их группами на отрезке, а затем, согласно кривой Пеано, отобразить эти точки на квадрат и построить ребра графа. Так как плотные множества располагаются плотно на отрезке, то и на квадрате они будут

занимать компактные области. Такое изображение графа хорошо покажет связи между его плотными подграфами.
Джои Бартольди (John J. Bartholdi) в своей статье [12] описывает применение кривой Пеано к задаче коммивояжера. Там предлагается наложить на схему города кривую Пеано и посещать точки в той последовательности, как их посещает кривая Пеано.
Известным приложением кривых является обработка изображений ([17], [18], [19], [26]). Двумерное изображение (черно-белое, серое или цветное) можно представлять в виде функции f(x,y), определенной на (цифровом) прямоугольнике. Пусть p(t) пеановская кривая, отображающая отрезок на этот прямоугольник. Тогда композиция f(p(t)) представляет собой функцию одной переменной, которую можно сжимать (с потерей информации), например, с помощью разложения по всплескам (wawelet). Такого рода представление хорошо согласуется с алгоритмом JPEG-2000 и также позволяет делать Zoom: раскодирование части изображения.
Чтобы с успехом применять кривые Пеано, нужно знать некоторые их свойства. Например, в приложениях, где требуется обход (сканирование) многомерной решетки, обычно необходимо знать насколько далеко кривая уходит от заданной точки за определенное время. В разных случаях для различных кривых применялись различные способы это измерить ([5],[6],[9]). Одним из таких способов является так называемое квадратно-линейное отношение, определенное следующим образом:
Для пары p(t), р(г) точек1 кривой Пеано р: [0,1] —> [0,1] х [0,1] величина
|рД) -р(т)|2 t-r
называется квадратно-линейным отношением кривой р на этой паре. Верхняя грань квадратно-линейных отношений для всевозможных пар различных точек кривой называется квадратно-линейным отношением кривой.
Впервые задача о нахождении квадратно-линейного отношения для кривой Пеано была поставлена в статье [9] Готсмана и Линденбаума в 1996 году. В ней доказано, что квадратно-линейное отношение произвольной правильно кривой Пеано не может быть меньше 3, и найдена оценка сверху на квадратно-линейное отношение кривой Пеано-Гильберта равная б|.
В 1997 году вышла статья [6], в которой улучшена оценка сверху для квадратно-линейного отношения кривой Пеано-Гильберта. Доказано, что это отношение не превосходит 6.01. Также в этой статье исследована кривая Сер-пинского, оценка сверху для ее квадратно-линейного растяжения составила 4. Заметим: хотя данная кривая и заметает квадрат, но правильной квадратной
'Точкой кривой мы называем точку ее графика. То есть точка кривой Пеано — это по существу пара t,p(t), где t принадлежит отображаемому отрезку, p(t) — квадрату-образу.

А так как фракция т+ 1 подразделения, содержащая В не содержит В, то по крайней мере одна из координат В' превосходит соответствующую координату точки В не менее чем на (т+1)/2 — длину стороны квадрата фракции подразделения т+1. Пусть А имеет координаты А и Л2; В имеет координаты В і, В2 В' имеет координаты В[, В'2 соответственно. Предположим, для определенности, что В[ — Ві > В'2 — В2- Тогда
- в>а (3.3)
Для квадратно-линейного отношения пары (а, Ъ') на основе неравенств 3.2 и
3.3 полагая х = получаем такое неравенство
(В[ — А)2 + (В2 — А2)2 > (.Ві - А)2 + 2хДд{В, - АД + (В2 - А)2
Ь' — а Ь — а + х2
Для доказательства, что квадратно-линейное отношение пары (а, Ъ') превосходит отношение пары (а, b) при достаточно большом т, достаточно убедится, что производная но х от последней дроби положительна при х = 0. □
Лемма 17. Для любого вещественного нецелого числа х и любого натурального q найдется такое к, что дробная часть числа xqk не превосходит
Доказательство. Предположение противного приводит к тому что в ç-ичной системе счисления дробная часть х представится в виде бесконечной дроби состоящей из максимальных цифр. Но такая дробь представляет единицу. □
Лемма 18. Пусть А = р{а) и В = р(Ь) обозначают две точки единичного квадрата-образа правильной кривой Пеано p(t) рода g, у которых различны между собой ординаты, тогда как абсциссы совпадают. Если В не лежит на горизонтальной (параллельной оси абсцисс) стороне некоторой фракции (некоторого подразделения) кривой р, то существует сколь угодно близкая к В точка В' — р(Ь'), с той же абсциссой, что и В, такая что квадратнолинейное отношение пары (а,Ь') больше чем у пары (а,Ь).
Доказательство. Ординату точки квадрата Z будем обозначать Im Z. Будем считать, что В выше чем А, то есть имеет большую ординату Im Л > Im А Предположим, что В не принадлежит горизонтальной границе никакой фракции никакого подразделения. В силу леммы 17, примененной к Im В (для q = Дд), найдется к, для которого верхняя граница фракции F подразделения номер к, содержащая В, находится от В на расстоянии > д~(к+1У2. Обозначим через А і* временной интервал между b и точкой В' верхней границы F с той же абсциссой, что и В, ордината которой на Дгд > д~к+12 больше чем у В.