Straight skeleton

Материал из Викиконспекты
Перейти к: навигация, поиск
Эта статья находится в разработке!

Существует целый класс структур типа [math]\mathrm{skeleton}[/math], которые описывают базовые топологические свойства объектов. Структура [math]\mathrm{straight}\ \mathrm{skeleton}[/math] была придумала Oswin Aichholzer[1]. Она используются в различных практических задачах, а также для доказательства некоторых теорем[2].

Топологические свойства

Определение:
Straight skeleton (Angular Bisector Network, ABN) полигона без самопересечений определяет разбиение полигона на регионы, границами которых являются стороны полигона, биссектрисы углов и отрезки, соединяющие точки пересечения биссектрис.
Straight skeleton definition.png

Опишем подробней, как получается такое разбиение. Мы можем представить, будто все стороны прямоугольника параллельно двигаются внутрь с одинаковой постоянной скоростью. Тогда вершины будут двигаться вдоль биссектрис , а точки пересечения биссектрис будут соединять совпавшие участки сторон прямоугольника в конце движения. В каждый момент времени от начала движения рёбер мы получаем слоистую структуру (рис 1.). Чем-то она похожа на строение крыши в домах (рис. 3). На рис. 2 синим цветом выделен [math] \mathrm{straight}\ \mathrm{skeleton} [/math] — множество отрезков, образованных точками пересечения при движении сторон полигона.

Sk example1.jpg

Свойства дерева Straigh skeleton

TODO: Леммы о свойствах структуры Straight skeleton

Wavefront-алгоритм

TODO: Алгоритм построения простой за n^3 log n (wavefront)

Для монотонных многоугольников

TODO: Алгоритм для монотонных многоугольников за n log n

Сложный алгоритм

TODO: Алгоритм в общем виде за n*m + n log n

Примечания

Источники информации