Псевдотреугольник

Псевдотреугольник между тремя гладкими выпуклыми множествами (слева) и многоугольный псевдотреугольник (справа).

В евклидовой плоской геометрии псевдотреугольник выпуклыми ( псевдотреугольник ) — односвязное подмножество плоскости , лежащее между любыми тремя взаимно касающимися множествами . Псевдотриангуляция ) — ( псевдотриангуляции это разбиение области плоскости на псевдотреугольники, а заостренная псевдотриангуляция — это псевдотриангуляция, в которой в каждой вершине инцидентные ребра охватывают угол меньше π.

Хотя слова «псевдотреугольник» и «псевдотриангуляция» использовались в математике в различных значениях гораздо дольше, Используемые здесь термины были введены в 1993 году Мишелем Поччиолой и Гертом Вегтером в связи с вычислением отношений видимости и бикасательных между выпуклыми препятствиями на плоскости. Заостренные псевдотриангуляции были впервые рассмотрены Илеаной Стрейну (2000, 2005) как часть ее решения проблемы плотничьей линейки , доказательства того, что любой простой многоугольный путь на плоскости можно выпрямить с помощью последовательности непрерывных движений. Псевдотриангуляции также использовались для обнаружения столкновений движущихся объектов. а также для динамического рисования графиков и морфинга фигур. Заостренные псевдотриангуляции возникают в теории жесткости как примеры минимально жестких плоских графов . и в методах размещения охраны в связи с теоремой о художественной галерее . Обстреливающий антиматроид плоского множества точек приводит к заостренным псевдотриангуляциям: хотя не все заостренные псевдотриангуляции могут возникнуть таким образом.

Подробный обзор большей части обсуждаемого здесь материала см. в Rote, Santos и Streinu (2008).

Псевдотреугольники

(Pocchiola & Vegter 1996a , 1996b , 1996c ) первоначально определяли псевдотреугольник как односвязную область плоскости, ограниченную тремя гладкими выпуклыми кривыми, касающимися в своих конечных точках. Однако последующая работа остановилась на более широком определении, которое в более общем смысле применимо к многоугольникам , а также к областям, ограниченным гладкими кривыми, и допускает ненулевые углы в трех вершинах. В этом более широком определении псевдотреугольник — это односвязная область плоскости, имеющая три выпуклые вершины. Три граничные кривые, соединяющие эти три вершины, должны быть выпуклыми в том смысле, что любой отрезок, соединяющий две точки одной и той же граничной кривой, должен полностью лежать вне или на границе псевдотреугольника. Таким образом, псевдотреугольник — это область между выпуклыми оболочками этих трех кривых, и, в более общем смысле, любые три взаимно касающихся выпуклых множества образуют псевдотреугольник, который лежит между ними.

Для алгоритмических приложений особый интерес представляет характеристика псевдотреугольников, которые являются многоугольниками. В многоугольнике вершина является выпуклой , если она охватывает внутренний угол меньше π, и вогнутой в противном случае (в частности, мы считаем вогнутым угол ровно π). Любой многоугольник должен иметь как минимум три выпуклых угла, поскольку общий внешний угол многоугольника равен 2π, каждый из выпуклых углов вносит в эту сумму менее π, а вогнутые углы вносят нулевой или отрицательный вклад. Многоугольный псевдотреугольник — это многоугольник, имеющий ровно три выпуклые вершины. В частности, любой треугольник и любой невыпуклый четырехугольник являются псевдотреугольниками.

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

Псевдотриангуляции

Псевдотриангуляция – это разбиение области плоскости на псевдотреугольники. Любая триангуляция области плоскости является псевдотриангуляцией. Хотя любые две триангуляции одной и той же области должны иметь одинаковое количество ребер и треугольников, этого нельзя сказать о псевдотриангуляциях; например, если область сама является многоугольным псевдотреугольником с n - вершинами, то ее псевдотриангуляция может иметь от одного псевдотреугольника и n ребер до n - 2 псевдотреугольников и 2 n - 3 ребер.

Минимальная псевдотриангуляция — это псевдотриангуляция T такая, что ни один подграф T не является псевдотриангуляцией, охватывающей одну и ту же выпуклую область плоскости. Минимальная псевдотриангуляция с n вершинами должна иметь не менее 2 n − 3 ребер; если он имеет ровно 2 n - 3 ребра, это должна быть заостренная псевдотриангуляция, но существуют минимальные псевдотриангуляции с 3 n - O(1) ребрами.

Агарвал и др. (2002) описывают структуры данных для поддержки псевдотриангуляций движущихся точек или движущихся многоугольников. Они показывают, что использование псевдотриангуляций вместо триангуляций позволяет их алгоритмам поддерживать эти структуры с относительно небольшими комбинаторными изменениями по мере движения входных данных, и они используют эти динамические псевдотриангуляции для обнаружения столкновений между движущимися объектами.

Гудмундссон и др. (2004) рассматривают проблему поиска псевдотриангуляции множества точек или многоугольника с минимальной общей длиной ребра и предлагают алгоритмы аппроксимации для этой проблемы.

Заостренные псевдотриангуляции

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

можно Заостренную псевдотриангуляцию определить как конечный непересекающийся набор отрезков прямой, такой, что в каждой вершине инцидентные отрезки прямой охватывают угол не более π, и такой, что никакие отрезки прямой не могут быть добавлены между любыми двумя существующими вершинами, сохраняя при этом это свойство. Нетрудно видеть, что заостренная псевдотриангуляция является псевдотриангуляцией своей выпуклой оболочки: все ребра выпуклой оболочки могут быть добавлены, сохраняя свойство охвата углов, а все внутренние грани должны быть псевдотреугольниками, иначе двухкасательный между двумя можно было бы добавить отрезок. вершины лица.

Заостренная псевдотриангуляция с v вершинами должна иметь ровно 2 v − 3 ребра. Это следует из простого аргумента двойного счета, включающего характеристику Эйлера : поскольку каждая грань, кроме внешней, представляет собой псевдотреугольник с тремя выпуклыми углами, псевдотриангуляция должна иметь 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 ребер. Таким образом, заостренные псевдотриангуляции удовлетворяют условиям, определяющим графы Ламана : они имеют ровно 2 v − 3 ребра, а их k -вершинные подграфы имеют не более 2 k − 3 ребер. Графы Ламана, а следовательно, и заостренные псевдотриангуляции, представляют собой минимально жесткие графы в двух измерениях. Каждый планарный граф Ламана можно нарисовать как точечную псевдотриангуляцию, хотя не каждое плоское изображение плоского графа Ламана является псевдотриангуляцией.

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

Айххольцер и др. (2004) показывают, что набор из n точек, h из которых принадлежат выпуклой оболочке множества, должен иметь не менее C _{h −2} ×3 ^{п - час} различные заостренные псевдотриангуляции, где C _i обозначает i- е каталанское число . Как следствие, они показывают, что множества точек с наименьшим количеством заостренных псевдотриангуляций являются множествами вершин выпуклых многоугольников. Айххольцер и др. (2006) исследуют множества точек с большим количеством заостренных псевдотриангуляций. Исследователи вычислительной геометрии также предоставили алгоритмы для составления списка всех точечных псевдотриангуляций набора точек за небольшой промежуток времени на каждую псевдотриангуляцию.

См. также

• Дельтовидная кривая
• Круглый треугольник

Ссылки

• Агарвал, Панкадж К .; Баш, Жюльен; Гибас, Леонидас Дж .; Хершбергер, Джон ; Чжан, Ли (2002), «Деформируемые мозаики свободного пространства для обнаружения кинетических столкновений», International Journal of Robotics Research , 21 (3): 179–197, doi : 10.1177/027836402320556395 , S2CID   11907465 .
• Айххольцер, Освин; Ауренхаммер, Франц ; Крассер, Ханнес; Спекманн, Беттина (2004), «Выпуклость минимизирует псевдотриангуляции», Теория и приложения вычислительной геометрии , 28 (1): 3–10, doi : 10.1016/j.comgeo.2004.01.002 , MR   2070708 . Предварительная версия в Канаде. Конф. Вычислить. Геом., 2002 .
• Айххольцер, Освин; Орден, Дэвид; Сантос, Франциско ; Спекманн, Беттина (2008), «О количестве псевдотриангуляций некоторых наборов точек», Журнал комбинаторной теории, серия A , 115 (2): 254–278, arXiv : math/0601747 , doi : 10.1016/j. jcta.2007.06.002 , МР   2382515 , S2CID   1189243
• Берег, Сергей (2005), «Перечисление псевдотриангуляций на плоскости», Вычислительная теория геометрии и приложения , 30 (3): 207–222, doi : 10.1016/j.comgeo.2004.09.002 , MR   2123970 .
• Брённиманн, Эрве; Кеттнер, Лутц; Поччиола, Мишель; Снойинк, Джек (2006), «Подсчет и перечисление точечных псевдотриангуляций с помощью жадного алгоритма флип» , SIAM Journal on Computing , 36 (3): 721–739, doi : 10.1137/050631008 , MR   2263009 .
• Гудмундссон, Иоахим; Левкопулос, Христос; Камаль, Лодая; Мина, Махаджан (2004), «Псевдотриангуляции с минимальным весом» (PDF) , в Лодая, Камаль; Махаджан, Мина (ред.), FSTTCS 2004: Основы программных технологий и теоретической информатики , Конспекты лекций по информатике, том. 3328, Springer-Verlag, стр. 299–310, arXiv : 0705.3888 , doi : 10.1007/b104325 , ISBN  978-3-540-24058-7 , S2CID   47024821 .
• Хаас, Рут ; Орден, Дэвид; Роте, Гюнтер; Сантос, Франциско ; Серватиус, Бриджит ; Серватий, Герман; Сувен, Диана ; Стрейну, Илеана ; Уайтли, Уолтер (2005), «Плоские минимально жесткие графы и псевдотриангуляции», Теория вычислительной геометрии и приложения , 31 (1–2): 31–61, arXiv : math/0307347 , doi : 10.1016/j.comgeo.2004.07 .003 , МР   2131802 , S2CID   38637747 .
• Хар-Пелед, Сариэль (2002), Комментарий к псевдотриангуляции в трех измерениях , заархивировано из оригинала 12 сентября 2006 г. , получено 12 апреля 2007 г.
• Поччиола, Мишель; Вегтер, Герт (1996a), «Комплекс видимости» , Международный журнал вычислительной геометрии и приложений , 6 (3): 297–308, doi : 10.1142/S0218195996000204 , заархивировано из оригинала 03 декабря 2006 г. Предварительная версия в девятом симпозиуме ACM. Вычислительная геометрия (1993) 328–337 .
• Поччиола, Мишель; Вегтер, Герт (1996b), «Топологически широкие комплексы видимости посредством псевдотриангуляции», Дискретная и вычислительная геометрия , 16 (4): 419–453, doi : 10.1007/BF02712876 , MR   1414964 .
• Поччиола, Мишель; Вегтер, Герт (1996c), «Псевдотриангуляции: теория и приложения» , Труды 12-го ежегодного симпозиума ACM по вычислительной геометрии , стр. 291–300, doi : 10.1145/237218.237398 , S2CID   15948239 .
• Роте, Гюнтер; Сантос, Франциско ; Стрейну, Илеана (2003), «Расширяющие движения и многогранник заостренных псевдотриангуляций», Дискретная и вычислительная геометрия — The Goodman-Pollack Festschrift , Springer-Verlag, стр. 699–736, arXiv : math.CO/0206027 , doi : 10.1007/978-3-642-55566-4_33 , S2CID   14689476 .
• Роте, Гюнтер; Сантос, Франциско ; Стрейну, Илеана (2008), «Псевдотриангуляции — обзор», Обзоры по дискретной и вычислительной геометрии , Современная математика, том. 453, Провиденс, Род-Айленд: Американское математическое общество, стр. 343–410, MR   2405689 .
• Роте, Гюнтер; Ван, Цао Ань; Ван, Лушэн; Сюй, Иньфэн (2003), «Об ограниченных минимальных псевдотриангуляциях» (PDF) , Вычисления и комбинаторика , Конспекты лекций по информатике, том. 2697, Springer-Verlag, стр. 445–454 .
• Шпекманн, Беттина ; Тот, Чаба Д. (2005), «Распределение вершинных π-защитных элементов в простых многоугольниках с помощью псевдотриангуляции», Discrete and Computational Geometry , 33 (2): 345–364, doi : 10.1007/s00454-004-1091-9 , МР   2121300 .
• Стрейну, Илеана (2000), «Комбинаторный подход к планарному планированию движения руки робота без столкновений» , Труды 41-го ежегодного симпозиума по основам компьютерных наук , Компьютерное общество IEEE, стр. 443–453, doi : 10.1109/SFCS. 2000.892132 , S2CID   9420124 .
• Стрейну, Илеана (2005), «Псевдотриангуляции, жесткость и планирование движения», Дискретная и вычислительная геометрия , 34 (4): 587–635, doi : 10.1007/s00454-005-1184-0 , MR   2173930 .
• Стрейну, Илеана (2006), «Механизмы параллельного перерисования, псевдотриангуляции и кинетические плоские графы», Proc. Межд. Симп. Рисование графиков (GD 2005) , Springer-Verlag, Конспекты лекций по информатике 3843, стр. 421–433 .