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

Московский государственный университет имени М.В. Ломоносова

0050557УЛ

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

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

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

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

2 9 НОЯ 2012

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

Москва — 2012

005055792

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

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

член-корреспондент РАН,

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

профессор Щепин Евгений Витальевич

(Математический институт

имени В.А. Стеклова РАН)

отдел геометрии и топологии

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

Дольников Владимир Леонидович доктор физико-математических наук, (ГОУ ВПО Ярославский государственный университет имени П.Г. Демидова) профессор кафедры теории функций и функционального анализа

Бесов Константин Олегович

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

(Математический институт

имени В.А. Стеклова РАН)

старший научный сотрудник

отдел дифференциальных уравнений

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

ГОУ ВПО "Горно-Алтайский государственный университет"

Защита диссертации состоится 21 декабря 2012 г. в 16 ч. 45 мин. на заседании диссертационного совета Д 501.001.84 при Московском государственном университете имени М.В. Ломоносова по адресу: РФ, 119991, Москва, ГСП-1, Ленинские горы, д.1, МГУ, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-математическ факультета МГУ (Главное здание, 14 этаж). Автореферат разослан 21 ноября 2012 г.

Ученый секретарь диссертационного совета Д 501.001.84 при МГУ доктор физико-математических наук, профессор

Иванов Александр Олегович

Общая характеристика работы Актуальность темы

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

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

Как и все фракталы, кривые Пеано активно используются в самых разных областях современной науки. В вычислительной математике они используются для численного интегрирования функций многих переменных. Ученые из Гарвардского университета в США пришли к выводу, что ДНК заполняет каждую клетку таким образом, что ее пространственная конструкция приближается к конструкции кривой Пеано.

В работе с базами данных4 5 кривые Пеано используются для преобразования многомерных данных к одномерным.

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

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

2D. Hilbert, "Uber die stetige Abbildung einer Linie auf ein Flachenstuck" Math. Annin., 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)

5R.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) Volume: 14, Issue: 6, Pages: 1301-1308

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

Джон Бартольди (John J. Bartholdi) в своей статье 7 описывает применение кривой Пеано к задаче коммивояжера. Там предлагается наложить на схему города кривую Пеано и посещать точки в той последовательности, как их посещает кривая Пеано.

Известным приложением кривых Пеано является обработка изображений8 9 10. Двумерное изображение (черно-белое, серое или цветное) можно представлять в виде функции f(x,y), определенной на (цифровом) прямоугольнике. Пусть p(t) пеановская кривая, отображающая отрезок на этот прямоугольник. Тогда композиция /(p(t)) представляет собой функцию одной переменной, которую можно сжимать (с потерей информации), например, с помощью разложения по всплескам (wawelet). Такого рода представление хорошо согласуется с алгоритмом JPEG-2000 и также позволяет делать Zoom: раскодирование части изображения.

Чтобы с успехом применять кривые Пеано, нужно знать некоторые их свойства. Например, в приложениях, где требуется обход (сканирование) многомерной решетки, обычно необходимо знать насколько далеко кривая уходит от заданной точки за определенное время. В разных случаях для различных кривых применялись различные способы это измерить111213. Одним из таких способов является так называемое квадратно-линейное отношение, определенное следующим образом: Для пары p(t), р(т) точек14 кривой Пеано р [0,1] —> [0,1] х [0,1] ве-

7 John J. Bartholdi, III, "A routing system based oil spacefilling curves" 1995

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

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

10M.Wattenberg, "A Note on Space-filling Visualizations and Space-filling Curves "INFO VIS 2005

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

12R.Niedermeier, K.Reinhardt, P.Sanders, "Towards Optimal Locality in Mesh-Indexing"Lecture Notes in Computer Science, 1997, Volume 1279/1997, 364-375

13H.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, 2010

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

личина

|p(*)-p(r)|2

\t-r\

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

Впервые задача о нахождении квадратно-линейного отношения15 для фиксированной кривой Пеано была поставлена в статье16 Готсмана и Линденбаума в 1996 году. В ней доказано, что квадратно-линейное отношение произвольной правильно кривой Пеано не может быть меньше 3, и найдена оценка сверху на квадратно-линейное отношение кривой Пеано-Гильберта равная

В 1997 году вышла статья17, в которой улучшена оценка сверху для квадратно-линейного отношения кривой Пеано-Гильберта. Доказано, что это отношение не превосходит 6.01. Также в этой статье исследованна кривая Серпинского, оценка сверху для ее квадратно-линейного растяжения составила 4. Заметим: хотя кривая Серпинского и заметает квадрат, но правильной квадратной кривой Пеано она не является, в силу того, что каждая фракция второго шага имеет форму треугольника, то есть фактически это правильная треугольная кривая. Кроме того в данной статье доказана оценка снизу для квадратно-линейного отношения любой кривой Пеано равная 3^ и оценка снизу для циклических кривых Пеано равная 4.

В 2004 году в свет вышла статья18 Щепина, в которой введено понятие правильных квадратных кривых Пеано и доказана оценка снизу равная 5 для любой квадратной кривой Пеано, у которой начало и конец лежат в вершинах квадрата. В частности, это утверждение верно для кривых, у которых при построении второго шага используются повороты и перемещения фракций, но не обращение времени. Такой класс кривых мы называем классом изотонных квадратных кривых. Класс кривых, определенный Щепиным, допускает обращение времени — значит, он со-

15под названием "Locality"

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

17R.Niedermeier, K.Reinhardt, P.Sanders, "Towards Optimal Locality in Mesh-Indexing"Lecture Notes in Computer Science, 1997, Volume 1279/1997, 364-375

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

держит в себе класс изотонных квадратных кривых.

Точное вычисление квадратно-линейного отношения для заданной правильной кривой Пеано представляет собой довольно трудную проблему. На данный момент квадратно-линейное отношение точно определено лишь для нескольких кривых. В их числе — изученная в данной работе кривая Пеано-Гильберта, для которой это отношение оказалось равным 6. Статья 19 с доказательством этого факта вышла в 2006 году. Позже, в 2010 году, на статью ссылаются авторы работы20, в которой доказывается, что нижняя оценка квадратно-линейного отношения для любой кривой Пеано равна четырем.

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

Интересно было найти кривые с квадратно-линейным отношением меньшим, чем в классическом случае. И они были обнаружены в классе правильных кривых Пеано фрактального рода 9. В пятой главе данной диссертации доказано, что кривые Пеано рода 9 могут быть либо диагональными, либо односторонними, то есть начало и конец кривой располагаются либо в диагонально-противоположных, либо в соседних вершинах квадрата. И в том, и в другом случае удалось найти и полностью изучить класс кривых с минимальным квадратно-линейным отношением равным 5|. Результаты, связанные с диагональными кривыми опубликованы в статье 21 2008 года. А в пятой главе данной диссертации изучены односторонние кривые Пеано рода 9. Эти результаты опубликованы в статье 22 2011 года.

Цель работы

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

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

20H.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, 2010

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

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

2. Нахождение правильных кривых Пеано с наименьшим квадратно-линейным отношением.

3. Изучение свойств квадратно-линейного отношения правильных кривых Пеано.

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

В диссертации используются методы дискретной и комбинаторной геометрии. Автором найден удобный способ кодирования кривых, на основе которого реализована программа подсчета квадратно-линейного отношения правильных кривых Пеано. Кроме того, используется метод теоретического обоснования точности квадратно-линейных отношений, полученных с помощью компьютера, разработанный автором совместно с Щепиным Е.В.

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

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

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

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

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

4. Описаны все правильные фрактальные кривые Пеано рода 9 с квадратно-линейным отношением равным 5|.

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

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

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

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

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

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

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

Основные результаты диссертации неоднократно докладывались на семинаре отдела геометрии и топологии Математического института имени В.А.Стеклова РАН под руководством Щепина Е.В. (2008-2012г.), на семинарах Механико-математического факультета МГУ имени М.В. Ломоносова, в том числе неоднократно на семинаре "Дискретная геометрия и геометрия чисел" под руководством Долбилина Н.П. , Мощеви-тина Н.Г. и Щепина Е.В. (2008-2011г.), а так же на следующих международных конференциях: "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.

Публикации

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

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

Диссертация состоит из введения, пяти глав, списка литературы и приложения. Полный объем диссертации — 73 страницы, библиография включает 31 наименование.

Содержание работы

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

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

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

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

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

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

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

Вторая глава называется "Оценка снизу квадратно-линейного отношения правильных кривых Пеано". В параграфе 2.1 приведены известные оценки для широкого класса кривых и для некоторого множества правильных кривых Пеано.

Основной теоремой параграфа 2.2 является Теорема У любой правильной кривой Пеано начальная и конечная точки находятся либо в вершинах квадрата, либо одна из них в вершине, а другая в середине противоположной стороны.

. Щепин в своей статье23 обосновал оценку равную 5 для правильных кривых Пеано, имеющих свое начало и конец в вершинах квадрата. В параграфе 2.3 введен класс К — множество правильных кривых Пеано с началом в вершине квадрата и концом в середине противоположной

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

стороны. Также в параграфе доказана

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

В параграфе 2.4 собраны вместе все утверждения, позволяющие обосновать более общую теорему:

Теорема Всякая правильная квадратная кривая Пеано имеет квадратно-линейное отношение не меньшее 5.

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

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

А также доказана

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

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

Четвертая глава называется "Кодирование правильных кривых Пеано".

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

Во второй части четвертой главы приведено описание реализованной автором программы, которая позволяет вычислять квадратно-линейное

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

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

' В пятой главе исследован класс правильных пеановских кривых фрактального рода 9.

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

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

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

Теорема Квадратно-линейное отношение кривых из класса минимальных правильных односторонних кривых Пеано фрактального рода 9 равно 5|.

Тем самым данная глава дополняет статью [3] и завершает рассмотрение правильных кривых Пеано фрактального рода 9 в поисках кривых с минимальным квадратно-линейным отношением.

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

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

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

становку задач и постоянное внимание к работе.

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

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

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

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

(Соискателем доказана теорема о рациональности квадратно- линейного отношения у любой правильной квадратной кривой Пеано)

Отпечатано в отделе оперативной печати Геологического ф-та МГУ Тираж ГОО экз. Заказ Кг 61

Введение

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] величина

1Р(*)-РСГ)|2 t-T\ называется квадратно-линейным отношением кривой р на этой паре. Верхняя грань квадратно-линейных отношений для всевозможных пар различных точек кривой называется квадратно-линейным отношением кривой.

Впервые задача о нахождении квадратно-линейного отношения для кривой Пеано была поставлена в статье [9] Готсмана и Линденбаума в 1996 году. В ней доказано, что квадратно-линейное отношение произвольной правильно кривой Пеано не может быть меньше 3, и найдена оценка сверху на квадратно-линейное отношение кривой Пеано-Гильберта равная б|.

В 1997 году вышла статья [6], в которой улучшена оценка сверху для квадратно-линейного отношения кривой Пеано-Гильберта. Доказано, что это отношение не превосходит 6.01. Также в этой статье исследована кривая Сер-пинского, оценка сверху для ее квадратно-линейного растяжения составила 4. Заметим: хотя данная кривая и заметает квадрат, но правильной квадратной

1 Точкой кривой мы называем точку ее графика. То есть точка кривой Пеано — это по существу пара t,p(t), где t принадлежит отображаемому отрезку, p(t) — квадрату-образу. кривой Пеано она не является, в силу того, что каждая фракция второго шага имеет форму треугольника, то есть фактически это треугольная кривая. Кроме того в данной статье доказана оценка снизу для квадратно-линейного отношения любой кривой Пеано равная 3| и оценка снизу для циклических кривых Пеано равная 4.

В 2004 году в свет вышла статья Щепина ([2]), в которой введено понятие правильных квадратных кривых Пеано и доказана оценка снизу равная 5 для любой квадратной кривой Пеано, у которой начало и конец лежат в вершинах квадрата. В частности, это утверждение верно для кривых, у которых при построении второго шага используются повороты и перемещения фракций, но не обращение времени. Такой класс кривых мы называем классом изотонных квадратных кривых. Немецкий математик Вундерлих (ХУипскНсЬ) описывал его в статье [4]. Класс кривых, определенный Щепииым, допускает обращение времени — значит, он содержит в себе класс изотонных квадратных кривых.

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

И).

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

Интересно было найти кривые с квадратно-линейным отношением меньшим, чем в классическом случае. И они были обнаружены в классе правильных кривых Пеано фрактального рода 9. В пятой главе данной диссертации доказано, что кривые Пеано рода 9 могут быть либо диагональными, либо односторонними, то есть начало и конец кривой располагаются либо в диагонально-противоположных, либо в соседних вершинах квадрата. И в том, и в другом случае удалось найти и полностью изучить класс кривых с минимальным квадратно-линейным отношением равным 5§. Результаты, связанные с диагональными кривыми опубликованы в статьях [31] и [30]. А в пятой главе данной диссертации изучены односторонние кривые Пеано рода 9. Эти результаты опубликованы в статье [29].

Диссертация состоит из введения, пяти глав, списка литературы и приложения.