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

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

На правах рукописи

УДК 519.6

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

О КВАДРАТНО-ЛИНЕЙНОМ ОТНОШЕНИИ

ПРАВИЛЬНЫХ КРИВЫХ ПЕАНО

Специальность

01.01.04 геометрия и топология

АВТОРЕФЕРАТ

Москва 2011

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

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

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

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

доктор физико-математических наук, профессор ЯрГУ Владимир Леонидович Дольников кандидат физико-математических наук научный сотрудник Математический институт им. В. А. Стеклова РАН Константин Олегович Бесов

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

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

Защита диссертации состоится 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.

На последнем приложении остановимся поподробнее. Двумерное изображение (черно-белое, серое или цветное) можно представлять в виде функции f (x, y), определенной на (цифровом) прямоугольнике. Пусть p(t) пеановская кривая, отображающая отрезок на этот прямоугольник.

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

G. Peano, "Sur une courbe, qui remplit toute une aire plane" Math. Ann., 36(1):157–160, D. Hilbert, "Uber die stetige Abbildung einer Linie auf ein Flachenstuck"Math. Annln., 38, 459-460, H. Sagan, "Space-Filling curves" Universitext series, Springer, 1994.

G.Jin, J.Mellor-Crummey, "Using Space-lling Curves for Computation Reordering"(LACSI 2005) R.Gutman, "Space-lling Curves in Geospatial Applications"Dr. Dobb’s Journal, July C.Muelder, Kwan-Liu Ma, "Rapid Graph Layout Using Space-lling Curves"Computer (2008) Volume: 14, Issue: 6, Pages: 1301- M. J. Aftosmis, M. J. Berger, S. M. Murman, "Applications of Space-Filling Curves to Cartesian Methods for CFD"Technical Report NAS-04- J.Valantinas, "On The Use of Space-lling Curves in Changing Image Dimensionality"Information Technology And Control, Kaunas, Technologija, 2005, Vol. 34, No. 4, 345 - 354.

R.Dafner, D.Cohen-Or, Y.Matias, "Context-based Space Fillin Curves"EUROGRAPHICS, vol. 19, no. 3, 2000.

M.Wattenberg, "A Note on Space-lling Visualizations and Space-lling Curves"INFOVIS 2005.

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

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

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

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

C.Gotsman, M.Lindenbaum, "On The Metric Properties of Discrete Space-lling Curves" IEEE transactions on image processing, vol. 5 no. 5 may R.Niedermeier, K.Reinhardt, P.Sanders,"Towards Optimal Locality in Mesh-Indexing"Lecture Notes in Computer Science, 1997, Volume 1279/1997, 364- Е.В. Щепин, "О фрактальных кривых Пеано" Труды МИАН, т. 247, стр. 204–303, W. Wunderlich, "Uber Peano-Kurven" Elemente der Mathematik, 28(1):1-10, 1973.

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

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

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

Данная часть работы была опубликована в двух статьях ([3],[4]).

H.Haverkort, F.Walderveen, "Locality and Bounding-Box Quality of Two-Dimensional Space-Filling Curves"Journal Computational Geometry: Theory and Applications Volume 43 Issue 2, February, Цель работы 1. Разработать метод, позволяющий находить квадратно-линейное отношение для любой кривой Пеано.

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

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

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

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

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

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

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

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

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

Найденый класс минимальных кривых рода 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 доказана лемма, позволяющая определять моменты прохождения кривой углов фракций любого шага построения кривой. Подcчитаны угловые моменты кривой Пеано Гильберта и в явном виде предъявлена пара точек с квадратно-линейным отношением равным шести.

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

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

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

Итак, основным результатом данной главы является:

Теорема Квадратно-линейное отношение кривой Пеано-Гильберта равно шести.

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

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

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

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

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

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

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

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

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

В параграфе 3.3 введено понятие особых точек, а именно:

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

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

Параграф 3.4 посвящен доказательству следующего факта:

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

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

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

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

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

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

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

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

В параграфе 3.8 обоснована стабилизация минимальной N -образной кривой на 6-м шаге построения, и на основе компьютерных вычислений доказано, что Теорема Квадратно-линейное отношение минимальной N -образной кривой Пеано равно 5 2.

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

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

В параграфе 4.2 доказана следующая лемма:

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

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

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

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

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

Публикации автора по теме диссертации 1. E. В. Щепин, К. Е. Бауман, “О кривых Пеано фрактального рода 9”, Моделирование и анализ данных: Труды факультета информационных технологий МГППУ, М.: РУСАВИА выпуск 1, стр. 79-89, 2. К. Е. Бауман, “Коэффицент растяжения кривой Пеано-Гильберта” Матем. заметки, том 80, № 5, стр. 643-656, 3. E. В. Щепин, К. Е. Бауман, “Минимальная кривая Пеано”, Геометрия, топология и математическая физика. I, Сборник статей. К 70-летию со дня рождения академика Сергея Петровича Новикова, Труды МИАН, т. 263, МАИК, М., 2008, 251– 4. К. Е. Бауман, “Односторонние кривые Пеано фрактального рода 9”, Труды МИАН, т. 275,