В евклидовой планарной геометрии псевдотреугольник ( псевдотреугольник ) — это односвязное подмножество плоскости , которое лежит между любыми тремя взаимно касательными выпуклыми множествами . Псевдотриангуляция ( псевдотриангуляции ) — это разбиение области плоскости на псевдотреугольники, а заостренная псевдотриангуляция — это псевдотриангуляция , в которой в каждой вершине инцидентные ребра охватывают угол меньше π.
Хотя слова «псевдотреугольник» и «псевдотриангуляция» использовались в различных значениях в математике гораздо дольше, [1] термины, используемые здесь, были введены в 1993 году Мишелем Поччиолой и Гертом Вегтером в связи с вычислением отношений видимости и касательных к двум точкам среди выпуклых препятствий на плоскости. Остроконечные псевдотриангуляции были впервые рассмотрены Илеаной Стрейну (2000, 2005) как часть ее решения задачи о линейке плотника , доказательства того, что любой простой многоугольный путь на плоскости может быть выпрямлен последовательностью непрерывных движений. Псевдотриангуляции также использовались для обнаружения столкновений между движущимися объектами [2] и для динамического рисования графов и морфинга форм. [3] Остроконечные псевдотриангуляции возникают в теории жесткости как примеры минимально жестких планарных графов [ 4] и в методах размещения охранников в связи с теоремой о художественной галерее . [5] Оболочечный антиматроид плоского множества точек приводит к образованию заостренных псевдотриангуляций, [6] хотя не все заостренные псевдотриангуляции могут возникать таким образом.
Подробный обзор большей части обсуждаемого здесь материала см. в работе Rote, Santos и Streinu (2008).
(Pocchiola & Vegter 1996a, 1996b, 1996c) изначально определили псевдотреугольник как односвязную область плоскости, ограниченную тремя гладкими выпуклыми кривыми, касающимися в своих конечных точках. [7] Однако последующая работа остановилась на более широком определении, которое применяется в более общем смысле к многоугольникам , а также к областям, ограниченным гладкими кривыми, и которое допускает ненулевые углы в трех вершинах. В этом более широком определении псевдотреугольник является односвязной областью плоскости, имеющей три выпуклые вершины. Три граничные кривые, соединяющие эти три вершины, должны быть выпуклыми в том смысле, что любой отрезок прямой, соединяющий две точки на одной и той же граничной кривой, должен полностью лежать вне или на границе псевдотреугольника. Таким образом, псевдотреугольник — это область между выпуклыми оболочками этих трех кривых, и, в более общем смысле, любые три взаимно касающихся выпуклых множества образуют псевдотреугольник, который лежит между ними.
Для алгоритмических приложений особый интерес представляет характеристика псевдотреугольников, которые являются многоугольниками. В многоугольнике вершина является выпуклой , если она охватывает внутренний угол меньше π, и вогнутой в противном случае (в частности, мы считаем угол ровно π вогнутым). Любой многоугольник должен иметь по крайней мере три выпуклых угла, поскольку общий внешний угол многоугольника равен 2π, выпуклые углы вносят вклад меньше π каждый в эту сумму, а вогнутые углы вносят нулевые или отрицательные величины. Многоугольный псевдотреугольник — это многоугольник, который имеет ровно три выпуклые вершины. В частности, любой треугольник и любой невыпуклый четырехугольник являются псевдотреугольниками.
Выпуклая оболочка любого псевдотреугольника является треугольником. Кривые вдоль границы псевдотреугольника между каждой парой выпуклых вершин либо лежат внутри треугольника, либо совпадают с одним из его ребер.
Псевдотриангуляция — это разбиение области плоскости на псевдотреугольники. Любая триангуляция области плоскости — это псевдотриангуляция. В то время как любые две триангуляции одной и той же области должны иметь одинаковое количество ребер и треугольников, то же самое не относится к псевдотриангуляциям; например, если область сама по себе является n -вершинным многоугольным псевдотреугольником, то ее псевдотриангуляция может иметь всего один псевдотреугольник и n ребер или всего n − 2 псевдотреугольников и 2 n − 3 ребра.
Минимальная псевдотриангуляция — это псевдотриангуляция T, такая, что ни один подграф T не является псевдотриангуляцией, покрывающей ту же самую выпуклую область плоскости. Минимальная псевдотриангуляция с n вершинами должна иметь по крайней мере 2 n − 3 ребра; если она имеет ровно 2 n − 3 ребра, она должна быть заостренной псевдотриангуляцией, но существуют минимальные псевдотриангуляции с 3 n − O(1) ребрами. [8]
Агарвал и др. (2002) описывают структуры данных для поддержания псевдотриангуляции движущихся точек или движущихся полигонов. Они показывают, что использование псевдотриангуляций вместо триангуляций позволяет их алгоритмам поддерживать эти структуры с относительно небольшими комбинаторными изменениями по мере перемещения входных данных, и они используют эти динамические псевдотриангуляции для выполнения обнаружения столкновений между движущимися объектами.
Гудмундссон и др. (2004) рассматривают задачу нахождения псевдотриангуляции множества точек или многоугольника с минимальной общей длиной ребра и предлагают алгоритмы аппроксимации для этой задачи.
Остроконечная псевдотриангуляция может быть определена как конечный непересекающийся набор отрезков прямых, такой, что в каждой вершине отрезки прямых охватывают угол не более π, и такой, что никакие отрезки прямых не могут быть добавлены между любыми двумя существующими вершинами, сохраняя это свойство. Нетрудно увидеть, что остроконечная псевдотриангуляция является псевдотриангуляцией ее выпуклой оболочки: все ребра выпуклой оболочки могут быть добавлены, сохраняя свойство охватывания углов, и все внутренние грани должны быть псевдотреугольниками, в противном случае между двумя вершинами грани может быть добавлен отрезок двойной касательной.
Остроконечная псевдотриангуляция с v вершинами должна иметь ровно 2 v − 3 ребра. [9] Это следует из простого аргумента двойного подсчета , включающего характеристику Эйлера : поскольку каждая грань, кроме внешней, является псевдотреугольником с тремя выпуклыми углами, псевдотриангуляция должна иметь 3 f − 3 выпуклых угла между соседними ребрами. Каждое ребро является ребром по часовой стрелке для двух углов, поэтому всего имеется 2 угла e , из которых все, кроме v, выпуклые. Таким образом, 3 f − 3 = 2 e − v . Объединение этого с уравнением Эйлера f − e + v = 2 и решение полученных одновременных линейных уравнений дает e = 2 v − 3. Тот же аргумент также показывает, что f = v − 1 (включая выпуклую оболочку как одну из граней), поэтому псевдотриангуляция должна иметь ровно v − 2 псевдотреугольников.
Аналогично, поскольку любой k -вершинный подграф заостренной псевдотриангуляции может быть завершен для формирования заостренной псевдотриангуляции его вершин, подграф должен иметь не более 2k − 3 ребер. Таким образом, заостренные псевдотриангуляции удовлетворяют условиям, определяющим графы Ламана : они имеют ровно 2v − 3 ребра, а их k -вершинные подграфы имеют не более 2k −3 ребер. Графы Ламана, а следовательно, и заостренные псевдотриангуляции, являются минимально жесткими графами в двух измерениях. Каждый планарный граф Ламана может быть нарисован как заостренная псевдотриангуляция, хотя не каждое планарное изображение планарного графа Ламана является псевдотриангуляцией. [10]
Другой способ найти заостренную псевдотриангуляцию — это шелушение множества точек; то есть удаление вершин выпуклой оболочки по одной, пока все точки не будут удалены. Семейство последовательностей удалений, которые могут быть сформированы таким образом, — это антиматроид шелушения множества точек, а множество ребер выпуклых оболочек последовательности множеств точек, образованных этим процессом удаления, образует псевдотриангуляцию. [6] Однако не все заостренные псевдотриангуляции могут быть сформированы таким образом.
Aichholzer et al. (2004) показывают, что набор из n точек, h из которых принадлежат выпуклой оболочке набора, должен иметь по крайней мере C h −2 ×3 n − h различных точечных псевдотриангуляций, где C i обозначает i- е число Каталана . Как следствие, они показывают, что наборы точек с наименьшим количеством точечных псевдотриангуляций являются наборами вершин выпуклых многоугольников. Aichholzer et al. (2006) исследуют наборы точек с большим количеством точечных псевдотриангуляций. Исследователи вычислительной геометрии также предоставили алгоритмы для перечисления всех точечных псевдотриангуляций набора точек за небольшое количество времени на псевдотриангуляцию. [11]