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

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

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

Структура

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

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

Свойства

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

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

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

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

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

См. также

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

Примечания
  1. Luzin et al, 2010.

Литература
  • Лузин С. Ю., Лячек Ю. Т., Петросян Г. С., Полубасов О. Б. Модели и алгоритмы автоматизированного проектирования радиоэлектронной и электронно-вычислительной аппаратуры. — СПб.: БХВ-Петербург, 2010. — 224 с. — ISBN 978-5-9775-0576-5.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.