Алгоритмы для динамических диаграмм Вороного

Золотов Борис Алексеевич
Бесплатно
В избранное
Работа доступна по лицензии Creative Commons:«Attribution» 4.0

Представлен первый сублинейный алгоритм обновления явно хранимого графа диаграммы Вороного при добавлении в диаграмму новой точки. Доказана верхняя оценка O(sqrt(n)) на количество комбинаторных изменений в границе ячейки прямой линии в диаграмме Вороного. Доказаны верхняя и нижняя оценки на количество порёберных склеек n равных квадратов.

1 Introduction 3
1.1 Voronoidiagrams……………………………….. 4
1.1.1 Combinatorial Changes to the Voronoi Diagram and the Flarb Operation . . 4
1.1.2 CostoftheFlarb……………………………. 6
1.2 Thecoinproblem……………………………….. 7
1.3 Gluingsofsquares ………………………………. 8
1.3.1 Chen—Hanalgorithmforgluingsofsquares ………………. 9
1.4 Mainresults………………………………….. 9
2 Sublinear algorithm for incremental Voronoi diagrams 9
2.1 DescriptionofDataStructure…………………………. 10
2.2 InsertionofaSite……………………………….. 11
2.3 RecognizingCellsWithChanges ……………………….. 11
2.3.1 Cell isBig………………………………. 11
2.3.2 Cell isSmall …………………………….. 12
2.4 ImplementingCombinatorialChanges …………………….. 12
2.4.1 ProcessingBigCells ………………………….. 12
2.4.2 ProcessingSmallCells…………………………. 14
2.5 WhenSmallCellsBecomeBig…………………………. 16
2.6 CorrectnessandTimeComplexity ………………………. 16
2.7 Discussionandopenproblems…………………………. 17
3 Estimating the number of combinatorial changes in a Voronoi diagram with sev- eral point sites and one line 17
3.1 VoronoidiagramsandDavenport–Schinzelsequences . . . . . . . . . . . . . . . . . 18
3.2 TreerepresentationofaDavenport–Schinzelsequence. . . . . . . . . . . . . . . . . 20
3.3 Theorderofrelabels……………………………… 21
3.4 InsertsandlengthofaDavenport–Schinzelsequence . . . . . . . . . . . . . . . . . 22
3.5 Proofofamortizedbound …………………………… 23
3.6 Discussionandopenproblems…………………………. 24
4 Bounds on the number of egde-to-edge gluings of squares 24
4.1 Algorithmtoclassifyedge-to-edgegluingsofsquares . . . . . . . . . . . . . . . . . . 27
4.2 Discussionandopenproblems…………………………. 27

Computational geometry studies computations on discrete geometric objects such as arrange- ments, diagrams, foldings and drawings. In particular one of its main interests is to design algorithms to construct such objects and data structures that store them efficiently.
The most crucial and defining concept applied in all those constructions is distance: whatever is studied, there is always some underlying metric that describes the object in question and defines its properties. It can be just the Euclidean metric, or some polyhedral metric, or any other metric that corresponds to a surface or a folding of a polygon.
In this thesis, we consider two different types of a distance metric. The Euclidean metric in R2 gives rise to the ordinary Voronoi diagrams, and we develop an algorithm that allows for fast update of a Voronoi diagram that is stored explicitly. We also consider polyhedral metrics of the spaces induced by gluing congruent squares edge to edge, and we propose a way to classify all such spaces in time polynomial in .
Even though there are many well-known algorithms that construct the Voronoi diagram for a given family of sites [9], the problem of making a Voronoi diagram dynamic, i. e. implementing changes to it when a new point site is inserted, has only drawn attention in the implicit case: maintaining implicit Voronoi diagram can be done in very little time [11, 12, 20]. Maintaining a Voronoi diagram explicitly has not yet been considered.
The worst one can expect is that when a new site is inserted, the number of updates in a Voronoi diagram (i. e. vertices and edges that change) is linear. This can happen for every insertion if we consider an embedded diagram and store the coordinates of all the vertices.
The situation improves if we consider the graph of the Voronoi diagram that is subject to com- binatorial changes: no coordinates matter, it is just deletion or addition of edges that is performed. In Allen et al. [2] it was proved that when a new site is inserted to a Voronoi diagram, only (√ ) combinatorial changes happen to the graph of the diagram. This opened a possibility to find a sublinear algorithm that finds and implements combinatorial changes in an explicitly stored graph of the Voronoi diagram.
In this thesis we present the first algorithm sublinear in (which is the number of sites) that does exactly that. The algorithm has running time of ̃( 3/4), which still does not achieve the (√ ) bound on the number of changes, that is why the quest for a better algorithm is still open.
One can try to employ the well-known «divide and conquer» strategy to find such an algorithm: divide all the sites into two halves by a line and update only the half of the diagram that receives the new site. We show that adding a line as a site to the diagram still allows for a (√ ) upper bound on the number of combinatorial changes per insertion. This means that, theoretically, «divide and conquer» is a desirable approach.
Another type of metrics and distances that can be often seen in computational geometry is polyhedral metrics and geodesic distances. A question concerning them that has been standing for a long time already is the Alexandrov’s problem of finding a convex polyhedron corresponding to a given polyhedral metric. There is almost no hope of solving this problem exactly for an arbitrary polyhedral metric, that is why several special cases are considered in literature [6, 8, 15, 16, 17].
A result we achieved in this thesis is a significant advance for an important special case: we present a polynomial-time algorithm to classify all the edge-to-edge gluing of at most squares. It is a development of my bachelor’s thesis making use of its results and an answer to a natural open question.
3
Our results open new directions for subsequent studies: it rises new questions that can be asked — like finding more efficient algorithms or enumerating gluings of other polygons, and suggests new possible methods that can be used to answer them.
This thesis is based in part on published articles and given talks: the part concerning sublinear explicit incremental planar Voronoi diagrams has been presented at JCDCG3 [4] and published in Journal for Information Processing [5], and the part concerning gluings of squares has been accepted for SoCG Young Researchers Forum 2021 [22]. The latter is a development of the bachelor’s thesis of the same author [26].
The rest of this section contains the main definitions and results that will be necessary for the main body of this thesis.

Заказать новую

Лучшие эксперты сервиса ждут твоего задания

от 5 000 ₽

Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям

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

    Хочешь уникальную работу?

    Больше 3 000 экспертов уже готовы начать работу над твоим проектом!

    Шагали Е. УрГЭУ 2007, Экономика, преподаватель
    4.4 (59 отзывов)
    Серьезно отношусь к тренировке собственного интеллекта, поэтому постоянно учусь сама и с удовольствием пишу для других. За 15 лет работы выполнила более 600 дипломов и... Читать все
    Серьезно отношусь к тренировке собственного интеллекта, поэтому постоянно учусь сама и с удовольствием пишу для других. За 15 лет работы выполнила более 600 дипломов и диссертаций, Есть любимые темы - они дешевле обойдутся, ибо в радость)
    #Кандидатские #Магистерские
    76 Выполненных работ
    Юлия К. ЮУрГУ (НИУ), г. Челябинск 2017, Институт естественных и т...
    5 (49 отзывов)
    Образование: ЮУрГУ (НИУ), Лингвистический центр, 2016 г. - диплом переводчика с английского языка (дополнительное образование); ЮУрГУ (НИУ), г. Челябинск, 2017 г. - ин... Читать все
    Образование: ЮУрГУ (НИУ), Лингвистический центр, 2016 г. - диплом переводчика с английского языка (дополнительное образование); ЮУрГУ (НИУ), г. Челябинск, 2017 г. - институт естественных и точных наук, защита диплома бакалавра по направлению элементоорганической химии; СПХФУ (СПХФА), 2020 г. - кафедра химической технологии, регулирование обращения лекарственных средств на фармацевтическом рынке, защита магистерской диссертации. При выполнении заказов на связи, отвечаю на все вопросы. Индивидуальный подход к каждому. Напишите - и мы договоримся!
    #Кандидатские #Магистерские
    55 Выполненных работ
    Ксения М. Курганский Государственный Университет 2009, Юридический...
    4.8 (105 отзывов)
    Работаю только по книгам, учебникам, статьям и диссертациям. Никогда не использую технические способы поднятия оригинальности. Только авторские работы. Стараюсь учитыв... Читать все
    Работаю только по книгам, учебникам, статьям и диссертациям. Никогда не использую технические способы поднятия оригинальности. Только авторские работы. Стараюсь учитывать все требования и пожелания.
    #Кандидатские #Магистерские
    213 Выполненных работ
    Петр П. кандидат наук
    4.2 (25 отзывов)
    Выполняю различные работы на заказ с 2014 года. В основном, курсовые проекты, дипломные и выпускные квалификационные работы бакалавриата, специалитета. Имею опыт напис... Читать все
    Выполняю различные работы на заказ с 2014 года. В основном, курсовые проекты, дипломные и выпускные квалификационные работы бакалавриата, специалитета. Имею опыт написания магистерских диссертаций. Направление - связь, телекоммуникации, информационная безопасность, информационные технологии, экономика. Пишу научные статьи уровня ВАК и РИНЦ. Работаю техническим директором интернет-провайдера, имею опыт работы ведущим сотрудником отдела информационной безопасности филиала одного из крупнейших банков. Образование - высшее профессиональное (в 2006 году окончил военную Академию связи в г. Санкт-Петербурге), послевузовское профессиональное (в 2018 году окончил аспирантуру Уральского федерального университета). Защитил диссертацию на соискание степени "кандидат технических наук" в 2020 году. В качестве хобби преподаю. Дисциплины - сети ЭВМ и телекоммуникации, информационная безопасность объектов критической информационной инфраструктуры.
    #Кандидатские #Магистерские
    33 Выполненных работы
    Оксана М. Восточноукраинский национальный университет, студент 4 - ...
    4.9 (37 отзывов)
    Возможно выполнение работ по правоведению и политологии. Имею высшее образование менеджера ВЭД и правоведа, защитила кандидатскую и докторскую диссертации по политоло... Читать все
    Возможно выполнение работ по правоведению и политологии. Имею высшее образование менеджера ВЭД и правоведа, защитила кандидатскую и докторскую диссертации по политологии.
    #Кандидатские #Магистерские
    68 Выполненных работ
    Евгений А. доктор, профессор
    5 (154 отзыва)
    Более 40 лет занимаюсь преподавательской деятельностью. Специалист в области философии, логики и социальной работы. Кандидатская диссертация - по логике, докторская - ... Читать все
    Более 40 лет занимаюсь преподавательской деятельностью. Специалист в области философии, логики и социальной работы. Кандидатская диссертация - по логике, докторская - по социальной работе.
    #Кандидатские #Магистерские
    260 Выполненных работ
    Татьяна С. кандидат наук
    4.9 (298 отзывов)
    Большой опыт работы. Кандидаты химических, биологических, технических, экономических, юридических, философских наук. Участие в НИОКР, Только актуальная литература (пос... Читать все
    Большой опыт работы. Кандидаты химических, биологических, технических, экономических, юридических, философских наук. Участие в НИОКР, Только актуальная литература (поставки напрямую с издательств), доступ к библиотеке диссертаций РГБ
    #Кандидатские #Магистерские
    551 Выполненная работа
    Дарья П. кандидат наук, доцент
    4.9 (20 отзывов)
    Профессиональный журналист, филолог со стажем более 10 лет. Имею профильную диссертацию по специализации "Радиовещание". Подробно и серьезно разрабатываю темы научных... Читать все
    Профессиональный журналист, филолог со стажем более 10 лет. Имею профильную диссертацию по специализации "Радиовещание". Подробно и серьезно разрабатываю темы научных исследований, связанных с журналистикой, филологией и литературой
    #Кандидатские #Магистерские
    33 Выполненных работы
    Вики Р.
    5 (44 отзыва)
    Наличие красного диплома УрГЮУ по специальности юрист. Опыт работы в профессии - сфера банкротства. Уровень выполняемых работ - до магистерских диссертаций. Написан... Читать все
    Наличие красного диплома УрГЮУ по специальности юрист. Опыт работы в профессии - сфера банкротства. Уровень выполняемых работ - до магистерских диссертаций. Написание письменных работ для меня в удовольствие.Всегда качественно.
    #Кандидатские #Магистерские
    60 Выполненных работ

    Другие учебные работы по предмету

    О локальных свойствах решений задач гидродинамики
    📅 2021год
    🏢 Санкт-Петербургский государственный университет
    Структуры комодулей на кольцах Чжоу флаговых многообразий
    📅 2021год
    🏢 Санкт-Петербургский государственный университет
    Полнота биортогональных систем для нескольких интервалов
    📅 2021год
    🏢 Санкт-Петербургский государственный университет
    Задача размещения элементов цепи поставок
    📅 2021год
    🏢 Санкт-Петербургский государственный университет