О квадратно-линейном отношении правильных кривых Пеано тема автореферата и диссертации по математике, 01.01.04 ВАК РФ

Математический институт им. В.А. Стеклова

Российская Академия Наук

4ВЭ#ои*>

На правах рукописи УДК 519.6

Бауман Константин Евгеньевич

О КВАДРАТНО-ЛИНЕЙНОМ ОТНОШЕНИИ ПРАВИЛЬНЫХ КРИВЫХ ПЕАНО

Специальность 01.01.04 — геометрия и топология

2 О ОКТ 2011

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва — 2011

4857605

Работа выполнена в отделе геометрии и топологии Математического ь статута им. В.А. Стеклова РАН.

Научный руководитель:

доктор физико-математических наук, ведущий научный сотрудник Математический институт им. В. А. Стеклова РА Евгений Витальевич Щепин

Официальные оппоненты:

доктор физико-математических наук, профессор ЯрГУ

Владимир Леонидович Дольников

кандидат физико-математических наук научный сотрудник

Математический институт им. В. А. Стеклова РА Константин Олегович Бесов

Ведущая организация:

Горно-Алтайский государственный университет

Защита диссертации состоится 3 ноября 2011 в 14 часов на заседай! диссертационного совета Д002.022.03 в Математическом институте и В.А. Стеклова Российской Академии Наук по адресу: 119991, Моске ул. Губкина, 8 (9 этаж).

С диссертацией можно ознакомиться в библиотеке Математического и статута им. В.А. Стеклова РАН.

Автореферат разослан 3 октября 2011 г.

Д002.022.03 в МИАН доктор физ.-мат. наук

Ученый секретарь диссертационного совета

Н.П. Долбил!

Общая характеристика работы

Актуальность темы

Данная диссертация посвящена изучению квадратно-линейного отношения кривых Пеано.

Под кривой Пеано подразумевается любое непрерывное отображение числового отрезка на плоский квадрат. Первая такая кривая была построена1 итальянским математиком Джузеппе Пеано в 1890 году. Через год Давид Гильберт предложил2 свой вариант кривой, ставший более известным за симметричность и простоту построения. С тех пор множество математиков, среди которых Лебег и Серпинский, строили свои варианты пеановских отображений. Hans Sagan в своей книге3 описывает наиболее известные варианты построения кривых Пеано.

Кривые Пеано широко используются в разных областях современной науки, таких как организация работы с базами данных4 5, анализ графов6, вычислительная гидродинамика7, обработка изображений8 9 10. На последнем приложении остановимся поподробнее. Двумерное изображение (черно-белое, серое или цветное) можно представлять в виде функции определенной на (цифровом) прямоугольнике. Пусть

){t) пеановская кривая, отображающая отрезок на этот прямоугольник. Тогда композиция f(p(t)) представляет собой функцию одной переменной, которую можно сжимать (с потерей информации), например, с помощью разложения по всплескам (wawelet). Такого рода представление :орошо согласуется с алгоритмом JPEG-2000 и также позволяет делать Zoom: раскодирование части изображения.

'G. Peano, "Sur une courbe, qui remplit toute une aire plane" Math. Ann., 36(X):157—160, 1890

2D. Hilbert, "Ubcr die stetige Abbildung eincr Linie auf cm Flachcnstuck" Math. Annln., 38, 459-460, 1891

3H. Sagan, "Space-Filling curves" Universitext series, Springer, 1994.

4G.Jin, J.Mellor-Crummey, "Using Space-filling Curves for Computation Reordering"(LACSI 2005)

sR.Gutman, "Space-filling Curves in Geospatial Applications"Dr. Dobb's Journal, July 1999

6C.Muelder, Kwan-Liu Ma, "Rapid Graph Layout Using Space-filling Curves"Computer (2008) 'olume: 14, Issue: 6, Pages: 1301-1308

7M. J. Aftosmis, M. J. Berger, S. M. Murman, "Applications of Space-Filling Curves to Cartesian lethods for CFD"Techiiical Report NAS-04-001

8J.VaIantinas, "On The Use of Space-filling Curves in Changing Image Dimensionality"Information echnology And Control, Kaunas, Tcchnologija, 2005, Vol. 34, No. 4, 345 - 354.

9R.Dafncr, D.Cohen-Ог, Y.Matias, "Context-based Space Fillin Curves"EUROGRAPHICS, vol. 19, o. 3, 2000.

10M. Watt enberg. "A Note on Space-filling Visualizations and Space-filling Curves"INFOVIS 2005.

Важной характеристикой кривых Пеано является так называем!. квадратно-линейное отношение. Для пары p(i), р(т) точек11 кривой Iii ано р [0,1] -> [0,1] х [0,1] величина

|*-т|

называется квадратно-линейным отношением кривой р на этой пар Верхняя грань квадратно-линейных отношений для всевозможных па различных точек кривой называется квадратно-линейным отношена ем кривой. Для приложений представляют интерес кривые с возможг меньшим квадратно-линейным отношением.

Впервые задача о нахождении квадратно-линейного отношения дл кривой Пеано была поставлена в статье12 Готсмана и Линденбаума в 19£ году. В 1997 году вышла статья13, в которой даются оценки сверху дл квадратно-линейного отношения кривой Пеано-Гильберта и кривой Се] пинского, а также доказываются оценка снизу для квадратно-линейно1 отношения любой кривой Пеано равная 3| и оценка снизу для циклич' ских кривых Пеано равная 4. В 2004 году в своей статье14 Щепин д< казывает оценку снизу равную 5 для любой квадратной кривой Пеан у которой при построении второго шага допускаются повороты и nepi мещение фракций, но не обращение времени. Такой класс кривых м называем классом Вундерлиха в честь немецкого математика, которь: его определил15.

Точное вычисление квадратно-линейного отношения для данной пр; вильной кривой Пеано представляет собой довольно трудную пробл му. На данный момент квадратно-линейное отношение точно определет лишь для нескольких кривых, среди которых изученная в работе крив? Пеано-Гильберта, и это отношение для нее оказалось равным 6. Стат! [2] с доказательством этого факта вышла в 2006 году. Позже, в 2010 год на нее ссылаются авторы статьи, в которой доказывается, что нижну

11Точкой кривой мы называем точку ее графика. То есть точка кривой Пеано — это по сущест пара t,p(t), где t принадлежит отображаемому отрезку, p(t) — квадрату-образу.

12C.Gotsman, M.Lindenbaum, "On The Metric Properties of Discrete Space-filling Curves" IEI transactions on image processing, vol. 5 no. 5 may 1996

13R.Niedermcier, K.Rcinhardt, P.Sanders, "Towards Optimal Locality in Mcsh-Indexing"Lccture Not in Computer Science, 1997, Volume 1279/1997, 364-375

14E.B. Щепин, "О фрактальных кривых Пеано" Труды МИЛН, т. 247, стр. 204-303, 2004

15W. Wunderlich, "Uber Peano-Kurven" Elemente der Mathematik, 28(1):1-10, 1973.

оценка квадратно-линейного отношения для любой кривой Пеано равна четырем16.

Кривая Пеано-Гильберта имеет фрактальный род 4, то есть делится на четыре части подобные целой кривой. Оригинальная кривая Пеано имеет фрактальный род 9. Квадратно-линейное отношение для этой кривой оказалось равным восьми.

Интересно было найти кривые с коэффициентом квадратно-линейного растяжения меньшим, чем в классическом случае. В работе полностью изучен класс кривых фрактального рода 9, и в нем найдено множество минимальных кривых с квадратно-линейным отношением равным 5|. Данная часть работы была опубликована в двух статьях ([3],[4]).

16H.Havcrkort, F.Walderveen, "Locality and Bounding-Box Quality of Two-Dimensional Space-Filling !urvcs"Journal Computational Geometry: Theory and Applications Volume 43 Issue 2, February, 2010

Цель работы

1. Разработать метод, позволяющий находить квадратно-линейное от ношение для любой кривой Пеано.

2. Исследовать кривые Пеано и найти среди них кривую с наймет шим квадратно-линейным отношением.

Основные методы исследования

В диссертации используются методы дискретной и комбинаторно геометрии. Кроме того, некоторые доказательства опираются на ко\< пыотерные вычисления.

Научная новизна

Основные результаты диссертации являются новыми и состоят в еле дующем:

1. Доказано, что квадратно-линейное отношение кривой Пеано- Гшп берта равно 6.

2. Доказано, что квадратно-линейное отношение произвольной крр вой Пеано есть рациональное число.

3. Среди кривых Пеано фрактального рода 9 найден и полностью изз чен класс минимальных кривых с квадратно-линейным отношеш ем равным 5|, то есть меньшим, чем у кривой Пеано-Гильберта.

Теоретическая и практическая ценность

Диссертация имеет теоретическую и практическую ценность.

Развитая в работе техника позволяет теоретически обосновывать на{ денные с помощью компьютера значения отношения.

Результаты, касающиеся определения точного значения квадратне линейного отношения, могут быть использованы для дальнейшей работ) в поисках кривой с минимальным квадратно-линейным отношением.

Найденый класс минимальных кривых рода 9 может быть испол! зован для приложений вместо классического варианта кривой, так ка квадратно-линейное отношение у таких кривых меньше.

Новый метод обозначения кривых, предложенный в диссертации, знг чительно упрощает процедуру кодирования.

Апробация результатов

Основные результаты диссертации докладывались на следующих международных конференциях: "24th Summer Conference on Topology and its Applications "July 14-17, 2009 Brno; "Topology, Geometry and Dynamics: Rokhlin Memorial"January 11-16, 2010 St .Petersburg, а также на семинарах механико-математического факультета МГУ, в том числе неоднократно на семинаре "Дискретная геометрия и геометрия чисел"под руководством Н.П. Долбилина, Н.Г. Мощевитина и Е.В.Щепина.

Публикации

Основные результаты диссертации опубликованы в четырех работах, список которых приведен в конце автореферата.

Структура диссертации

В первой вводной главе производится постановка задачи, описывается ее история возникновения, приводятся множество примеров приложения кривых Пеано, а также описывается структура диссертации, формулируются основные результаты.

Вторая глава посвящена изучению квадратно-линейного отношения кривой Пеано-Гильберта.

В параграфе 2.1 подробно описано построение кривой и приведено ее функциональное уравнение. В параграфе 2.2 доказана лемма, позволяющая определять моменты прохождения кривой углов фракций любого шага построения кривой. Подсчитаны угловые моменты кривой Пеано Гильберта и в явном виде предъявлена пара точек с квадратно-линейным отношением равным шести.

Параграф 2.1 посвящен доказательству того факта, что квадратно-линейное отношение для любой пары точек кривой Пеано-Гильберта не превосходит шести.

Квадратно-линейное отношение для явно заданной фрактальной кривой Пеано нетрудно определить с помощью компьютера. Однако, теоретическое обоснование того, что найденное компьютером значение действительно является наибольшим квадратно-линейным отношением, представляет значительные трудности.

Работа, описанная во второй главе, впервые дала такое теоретическое обоснование. Полученный результат относится к простейшей и самой известной кривой Пеано — кривой Пеано-Гильберта. Развитая в этой

работе техника использует высокую степень симметрии кривой Пеано-Гильберта и не переносится на случай менее симметричных кривых.

Итак, основным результатом данной главы является: Теорема Квадратно-линейное отношение кривой Пеано-Гилъберта равно шести.

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

Если для кривой Пеано-Гильберта ориентация фракций на втором шаге построения кривой однозначна, то в случае кривых фрактального рода 9 такой однозначности нет. Фактически, меняя ориентации фракций второго шага, мы получаем разные кривые. Количество таких кривых исчисляется сотнями.

Третья глава посвящена изучению диагональных кривых Пеано фраг тального рода 9. Среди них удалось обнаружить уникальную кривую с квадратно-линейным отношением 5|, то есть меньшим, чем у кривой Пеано-Гильберта. Мы будем называть эту кривую минимальной Ы-образной.

В данной главе приведено доказательство того, что квадратно- линейное отношение минимальной ^-образной кривой равно 5|. Оно основано на компьютерных вычислениях. Для обеспечения доказательности в этой главе построена теория, позволяющая делать точные заключения о квадратно-линейном отношении на основе компьютерных вычислений.

В параграфе 3.1 описаны реккурентные уравнения квадратных кривых Пеано, введено понятие центральной ломаной и цепного кода - средства для кодирования центральных кривых.

Первая кривая Пеано является диагональной и обладает фрактальным родом 9. В данном параграфе для ее квадратно-линейного отношения посчитана оценка снизу равная восьми. По аналогии с леммой из параграфа 2.2 подсчитаны угловые моменты минимальной ТУ-образной кривой.

Параграф 3.2 называется "Теорема единственности". В нем доказан следующий факт:

Теорема Существует единственная, с точностью до изометрии, диагональная ивановская кривая фрактального рода 9, отображающая единичный отрезок на единичный квадрат, которая имеет квадратно- линейное отношение меньше шести.

Теорема доказана на основе серии лемм, ограничивающих выбор ориентации фракций на втором шаге построения кривой.

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

Также доказана

Теорема Диагональная правильная кривая Пеано с квадратно-линейным отношением меньшим шести не имеет особых точек.

Параграф 3.4 посвящен доказательству следующего факта: Теорема Максимум квадратно-линейного отношения для правильной кривой Пеано моо/сет достигаться на паре углов или па паре особых точек некоторого подразделения. В последнем случае эта пара точек либо имеет одинаковые абсциссы и обе точки лежат на горизонтальных границах фракций, либо имеет одинаковые ординаты и обе точки принадлежат вертикальным границам фракций.

Важным следствием из теоремы является один из центральных результатов работы:

Следствие Для правильной кривой Пеапо, отображающей единичный отрезок на единичный квадрат, квадратно-линейное отношение является рациональным числом.

В параграфе 3.5 введено ключевое понятие, определяющее необходимый доказательный объем вычислений — понятие глубины правильной кривой Пеано.

Определение Ограничение кривой Пеано на пару соседних фрактальных периодов порядка к называется стыком порядка к этой кривой. Глубиной правильной фрактальной кривой Пеано называется наибольшее натуральное число й, для которого кривая имеет стык порядка <1, неподобный никакому стыку меньшего порядка.

Глубина кривой Пеано-Гильберта равна одному, а глубина минимальной ТУ-образной кривой равна двум. Можно показать, что глубина любой

правильной кривой Пеано не превосходит девяти.

В параграфе 3.6 введено вспомогательное понятие частичных квадра линейных отношений кривой, а в параграфе 3.7 доказаны некоторые неравенства для номера шага, после которого квадратно-линейное отношение на парах вершин фракций перестает расти. Такой шаг мы на зываем шагом стабилизации кривой.

В параграфе 3.8 обоснована стабилизация минимальной Л^-образной кривой на 6-м шаге построения, и на основе компьютерных вычислены доказано, что

Теорема Квадратно-линейное отношение минимальной N-образной щ вой Пеапо равно 5|.

Четвертая глава посвящена рассмотрению односторонних кривых Пс ано фрактального рода 9.

В параграфе 4.1 введен новый язык обозначения кривых, называемы вершинным кодом. Он сильно упрощает процедуру кодирования кривых, также с его помощью легко считать глубину.

В параграфе 4.2 доказана следующая лемма: Лемма Обходы всех правильных пеановских кривых рода 9 имеют сво начало и конец в угловых фракциях

В параграфе 4.3 доказана Теорема Квадратно-линейное отношение кривых Пеапо фрактальпог рода 9, обладающих диагональным переходом, строго больше 6.

В параграфе 4.4 подробно рассмотрены односторонние правильны пеановские кривые рода 9 без диагонального перехода, среди них вы делен класс минимальных кривых с квадратно-линейным отношение! равным 5|. Оказалось, что сущестуют четыре такие кривые, и они ста билизируются уже на пятом шаге. Аналогично параграфу 3.8 приведен доказательство теоремы:

Теорема Квадратно-линейное отношение кривых из класса минималъ них равно 5|.

В дополнение к предыдущей главе завершено рассмотрение кривы рода 9 в поисках кривой с минимальным квадратно-линейным отношением.

Благодарности

Автор выражает глубокую благодарность своему научному руководителю Евгению Витальевичу Щепину за постановку задач, их обсуждение и многолетнюю совместную работу.

Публикации автора по теме диссертации

1. Е. В. Щепин, К. Е. Бауман, "О кривых Пеано фрактального рода 9", Моделирование и анализ данных: Труды факультета информационных технологий МГППУ, М.: РУСАВИА выпуск 1, стр. 79-89, 2004

2. К. Е. Бауман, "Коэффицент растяжения кривой Пеано-Гильберта" Матем. заметки, том 80, № 5, стр. 643-656, 2006

3. Е. В. Щепин, К. Е. Бауман, "Минимальная кривая Пеано", Геометрия, топология и математическая физика. I, Сборник статей. К 70-летию со дня рождения академика Сергея Петровича Новикова, Труды МИАН, т. 263, МАИК, М., 2008, 251-271

4. К. Е. Бауман, "Односторонние кривые Пеано фрактального рода 9", Труды МИАН, т. 275, 2011