Квазитриангуляция

Квазитриангуляция — структура разбиения плоскости, обладающая свойствами триангуляции Делоне, но вершинами которой служат не точки, а произвольно наклонённые отрезки. Строго говоря, это разбиение не является триангуляцией в геометрическом смысле, то есть разбиением плоскости на треугольные грани, но является триангуляцией в топологическом смысле.

Квазитриангуляция. Чёрным цветом показаны отрезки топологии — квазивершины, серым — квазирёбра, белым — грани. Особенности квазирёбер: a — выпуклое четырёхугольное, b — невыпуклое четырёхугольное, c — треугольное, d — вырожденное, a и e — параллельные, f — квазиребро содержит часть отрезка.

Структура

Принцип построения структуры основан на (мысленной) замене каждого отрезка топологии на множество тесно (в пределе — бесконечно близко) расположенных точек и построения для всех этих точек триангуляции Делоне. Важно различать два типа граней: грани, инцидентные трём отрезкам, и грани, инцидентные только двум различным отрезкам. Грани второго типа группируются в кластеры — цепочки смежных граней, соединяющих одну и ту же пару отрезков. Если удалить все внутренние рёбра такой цепочки, то все грани цепочки объединяются в одно квазиребро (см. рис.). В общем случае, такое квазиребро имеет четырёхугольную форму, причём с двух противоположных сторон оно ограничено частями соединяемых отрезков, а с двух других — парой оставшихся не удалёнными рёбер. Для квазиребра эта пара не удалённых рёбер играет роль пары противоположно ориентированных квазидуг некоего квазиграфа. В топологическом смысле этот квазиграф является триангуляцией, то есть он планарен и все его грани — а это как раз грани первого типа — треугольные. Роль вершин квазиграфа играют отрезки.

Таким образом, плоскость разбивается на области двух видов: треугольные грани и, в общем случае, четырёхугольные квазирёбра. Граням инцидентны по три отрезка, а квазирёбрам — только по два. Квазирёбра могут в частных случаях вырождаться в отрезки прямой (в геометрическом смысле) или в треугольники, могут быть невыпуклыми четырёхугольниками и даже могут содержать внутри себя концевую часть отрезка (см. рис.). Если все вершины квазитриангуляции являются точками, то квазитриангуляция вырождается в триангуляцию Делоне, которая, таким образом, является частным случаем квазитриангуляции.

Свойства

1. Любая вершина квазитриангуляции всегда соединена ребром с ближайшей к ней вершиной.

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

3. Если грань инцидентна внутренней точке отрезка топологии, то этот отрезок направлен по касательной к окружности, описанной вокруг этой грани.

Доказательства свойств следуют из рассмотрения описанной выше «бесконечной» триангуляции Делоне: в обоих случаях рёбрами соединены одни и те же точки на отрезках, в обоих случаях грани одни и те же.

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

См. также

Триангуляция Делоне

Литература

• Лузин С. Ю., Лячек Ю. Т., Петросян Г. С., Полубасов О. Б. Модели и алгоритмы автоматизированного проектирования радиоэлектронной и электронно-вычислительной аппаратуры. — СПб.: БХВ-Петербург, 2010. — 224 с. — ISBN 978-5-9775-0576-5.