В евклидовой геометрии плоскости , A pseudotriangle ( pseudotriangle ) является односвязны подмножество плоскости , что лежит между любыми тремя взаимно касательный выпуклых множеств . Pseudotriangulation ( псевдо-триангуляции ) представляет собой разбиение области плоскости на pseudotriangles, а заостренный pseudotriangulation является pseudotriangulation , в котором в каждой вершине падающие кромки охватывают собой угол меньше , чем я.
Хотя слова «псевдотреугольник» и «псевдотриангуляция» использовались в математике в различных значениях гораздо дольше, [1] используемые здесь термины были введены в 1993 г. Мишелем Поккиолой и Гертом Вегтером в связи с вычислением отношений видимости и битангенсов. среди выпуклых препятствий на плоскости. Заостренные псевдотриангуляции были впервые рассмотрены Илеаной Стрейну (2000, 2005) как часть ее решения проблемы плотницкой линейки , доказательства того, что любой простой многоугольный путь на плоскости может быть выпрямлен последовательностью непрерывных движений. Псевдотриангуляции также использовались для обнаружения столкновений между движущимися объектами [2], а также для динамического рисования графиков и изменения формы. [3] Остроконечные pseudotriangulations возникают в теории жесткости в качестве примеров минимально жестких плоских графов , [4] и в способах размещения охранников в связи с теоремой картинной галереи . [5] обстреливать antimatroid из плоского множества точек приводит к заостренной pseudotriangulations, [6] , хотя не все острые pseudotriangulations могут возникнуть на этом пути.
Подробный обзор большей части обсуждаемого здесь материала см. В Rote, Santos , and Streinu (2008).
Псевдотреугольники
Поккиола и Вегтер (1996a, b, c) первоначально определили псевдотреугольник как односвязную область плоскости, ограниченную тремя гладкими выпуклыми кривыми, которые касаются своих концов. Однако последующая работа остановилась на более широком определении, которое в более общем плане применимо к многоугольникам, а также к областям, ограниченным гладкими кривыми, и которое допускает ненулевые углы в трех вершинах. В этом более широком определении псевдотреугольник - это односвязная область плоскости, имеющая три выпуклые вершины. Три граничные кривые, соединяющие эти три вершины, должны быть выпуклыми в том смысле, что любой отрезок прямой, соединяющий две точки на одной и той же граничной кривой, должен полностью лежать вне или на границе псевдотреугольника. Таким образом, псевдотреугольник - это область между выпуклыми оболочками этих трех кривых, и в более общем случае любые три взаимно касательных выпуклых множества образуют псевдотреугольник, который лежит между ними.
Для алгоритмических приложений особый интерес представляет характеризация псевдотреугольников, которые являются многоугольниками. В многоугольнике вершина является выпуклой, если она охватывает внутренний угол меньше π, и вогнутой в противном случае (в частности, мы считаем, что угол ровно π вогнутый). Любой многоугольник должен иметь как минимум три выпуклых угла, потому что общий внешний угол многоугольника равен 2π, каждый из выпуклых углов составляет меньше π, а вогнутые углы дают нулевой или отрицательный вклад. Многоугольный псевдотреугольник - это многоугольник, имеющий ровно три выпуклые вершины. В частности, любой треугольник и любой невыпуклый четырехугольник является псевдотреугольником.
Выпуклая оболочка любого pseudotriangle представляет собой треугольник. Кривые вдоль границы псевдотреугольника между каждой парой выпуклых вершин либо лежат внутри треугольника, либо совпадают с одним из его ребер.
Псевдотриангуляции
Pseudotriangulation является разбиение области плоскости на pseudotriangles. Любая триангуляция области плоскости является псевдотриангуляцией. В то время как любые две триангуляции одной и той же области должны иметь одинаковое количество ребер и треугольников, то же самое нельзя сказать о псевдотриангуляциях; например, если область сама является многоугольником с n- вершинами и псевдотреугольником, то ее псевдотриангуляция может иметь всего один псевдотреугольник и n ребер или до n - 2 псевдотреугольников и 2 n - 3 ребер.
Минимальное pseudotriangulation является pseudotriangulation Т , такие , что ни один подграф Т не является pseudotriangulation охватывающих ту же самую выпуклую область плоскости. Минимальная псевдотриангуляция с n вершинами должна иметь не менее 2 n - 3 ребер; если у него ровно 2 n - 3 ребра, это должна быть точечная псевдотриангуляция, но существуют минимальные псевдотриангуляции с 3 n - O (1) ребрами. [7]
Agarwal et al. (2002) описывают структуры данных для поддержки псевдотриангуляции движущихся точек или движущихся полигонов. Они показывают, что использование псевдотриангуляций вместо триангуляций позволяет их алгоритмам поддерживать эти структуры с относительно небольшими комбинаторными изменениями при перемещении входных данных, и они используют эти динамические псевдотриангуляции для обнаружения столкновений между движущимися объектами.
Gudmundsson et al. (2004) рассматривают задачу поиска псевдотриангуляции набора точек или многоугольника с минимальной общей длиной ребра и предоставляют алгоритмы аппроксимации для этой задачи.
Остроконечные псевдотриангуляции
Заостренное pseudotriangulation может быть определенно как конечный набор непересекающихся отрезков, таким образом, что в каждой вершине сегменты падающей линии охватывают угол в большем я, и таким образом, что никакие сегментов линии не могут быть добавлены между любыми двумя существующими вершинами, сохраняя при этом это свойство. Нетрудно видеть, что остроконечная псевдотриангуляция является псевдотриангуляцией ее выпуклой оболочки: все выпуклые края оболочки могут быть добавлены с сохранением свойства перекрытия углов, а все внутренние грани должны быть псевдотреугольниками, иначе между двумя может быть добавлен бит касательный отрезок прямой. вершины лица.
Точечная псевдотриангуляция с v вершинами должна иметь ровно 2 v - 3 ребра. [8] Это следует из простого аргумента двойного счета, включающего эйлерову характеристику : поскольку каждая грань, кроме внешней, является псевдотреугольником с тремя выпуклыми углами, псевдотриангуляция должна иметь 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 -вершинный подграф точечной псевдотриангуляции может быть завершен для образования точечной псевдотриангуляции его вершин, подграф должен иметь не более 2 k - 3 ребер. Таким образом, точечные псевдотриангуляции удовлетворяют условиям, определяющим графы Ламана : они имеют ровно 2 v - 3 ребра, а их подграфы с k -вершинами имеют не более 2 k - 3 ребер. Графы Ламана и, следовательно, также заостренные псевдотриангуляции, являются минимально жесткими графами в двух измерениях. Каждый плоский граф Ламана можно нарисовать как точечную псевдотриангуляцию, хотя не каждый планарный рисунок плоского графа Ламана является псевдотриангуляцией. [9]
Другой способ найти остроконечную псевдотриангуляцию - это оболочка набора точек; то есть удалять вершины выпуклой оболочки одну за другой, пока не будут удалены все точки. Семейство последовательностей удалений, которое может быть сформировано таким образом, является антиматроидом обстрела набора точек, а набор ребер выпуклых оболочек последовательности наборов точек, сформированных этим процессом удаления, образует псевдотриангуляцию. [6] Однако не все точечные псевдотриангуляции могут быть сформированы таким образом.
Aichholzer et al. (2004) показывают, что набор из n точек, h из которых принадлежат выпуклой оболочке набора, должен иметь не менее C h −2 × 3 n - h различных заостренных псевдотриангуляций, где C i обозначает i- е каталонское число . Как следствие, они показывают, что множества точек с наименьшим количеством заостренных псевдотриангуляций являются наборами вершин выпуклых многоугольников. Aichholzer et al. (2006) исследуют точечные множества с большим количеством заостренных псевдотриангуляций. Исследователи вычислительной геометрии также предоставили алгоритмы для перечисления всех указанных псевдотриангуляций набора точек за небольшой промежуток времени для каждой псевдотриангуляции. [10]
Смотрите также
Заметки
- ^ Для "псевдо-треугольник" смотри, например, Уайтхед, JHC (1961), "Коллекторы с поперечными полей в евклидовом пространстве", Annals математики , 73 (1): 154-212, DOI : 10,2307 / 1970286 , JSTOR 1970286 , Руководство по ремонту 0124917. На странице 196 эта статья ссылается на «условие псевдотреугольника» в функциональном приближении. Для «псевдотриангуляции» см., Например, Белага, È. Г. (1976), «[Векторы Хивуда псевдотриангуляций]», Доклады Академии Наук СССР , 231 (1): 14–17, MR 0447029..
- ^ Agarwal et al. (2002).
- ^ Streinu (2006).
- ^ Haas et al. (2005)
- ^ Спекманн и Тот (2005).
- ^ а б Хар-Пелед (2002).
- ^ Роте, Ван, Ван и Сюй (2003), теорема 4 и рисунок 4.
- ^ Впервые показано Streinu (2000), но аргумент, который мы приводим здесь, взят из Haas et al. (2005), лемма 5.
- ^ Haas et al. (2005).
- ↑ Берег (2005); Brönnimann et al. (2006).
Рекомендации
- Агарвал, Панкадж К .; Баш, Жюльен; Гибас, Леонидас Дж .; Хершбергер, Джон ; Чжан Ли (2002), "Деформируемое свободное пространство разбиения для кинетического обнаружения столкновений", Международный журнал Robotics Research , 21 (3): 179-197, DOI : 10,1177 / 027836402320556395.
- Айхольцер, Освин; Ауренхаммер, Франц ; Крассер, Ханнес; Speckmann, Беттина (2004), "Выпуклость сводит к минимуму псевдо-триангуляции", вычислительной теории геометрии и приложений , 28 (1): 3-10, DOI : 10.1016 / j.comgeo.2004.01.002 , МР 2070708. Предварительная версия в Канаде. Конф. Comput. Геом., 2002 .
- Айхольцер, Освин; Орден, Дэвид; Сантос, Франциско ; Спекманн, Беттина (2008), «О количестве псевдотриангуляций некоторых точечных множеств», Журнал комбинаторной теории, серия A , 115 (2): 254–278, arXiv : math / 0601747 , doi : 10.1016 / j. jcta.2007.06.002 , MR 2382515
- Берег, Сергей (2005), «Перечисление псевдотриангуляций на плоскости», Теория вычислительной геометрии и ее приложения , 30 (3): 207–222, doi : 10.1016 / j.comgeo.2004.09.002 , MR 2123970.
- Брённиманн, Эрве; Кеттнер, Лутц; Поккиола, Мишель; Snoeyink, Джек (2006), "Counting и перечисляя заостренные pseudotriangulations с помощью алгоритма жадного флип", SIAM журнал по вычислениям , 36 (3): 721-739, DOI : 10,1137 / 050631008 , MR 2263009.
- Гудмундссон, Иоахим; Левкопулос, Христос; Камаль, Лодая; Мина, Махаджан (2004), " Псевдотриангуляции минимального веса" (PDF) , в Лодая, Камаль; Mahajan, Мину (ред.), FSTTCS 2004: Основы технологии программного обеспечения и теоретической информатики , Lecture Notes в области компьютерных наук, 3328 , Springer-Verlag, стр пункты 299-310,. Arxiv : 0705,3888 , DOI : 10.1007 / b104325 , ISBN 978-3-540-24058-7.
- Хаас, Рут ; Орден, Дэвид; Роте, Гюнтер; Сантос, Франциско ; Серватиус, Бриджит ; Серватий, Герман; Сувейн, Дайан ; Стрейну, Илеана ; Уайтли, Уолтер (2005), «Плоские минимально жесткие графы и псевдотриангуляции», Теория вычислительной геометрии и приложения , 31 (1-2): 31–61, arXiv : math / 0307347 , doi : 10.1016 / j.comgeo.2004.07 .003 , Руководство по ремонту 2131802.
- Хар-Пелед, Сариэль (2002), Комментарий к псевдотриангуляции в трех измерениях , заархивирован из оригинала 12 сентября 2006 г. , извлечен 12 апреля 2007 г..
- Поккиола, Мишель; Vegter, Герт (1996a), "Видимость комплекс" , Международный журнал вычислительной геометрии и приложений , 6 (3): 297-308, DOI : 10,1142 / S0218195996000204 , заархивированы с оригинала на 2006-12-03. Предварительная версия в Девятом ACM Symp. Вычислительная геометрия (1993) 328–337 .
- Поккиола, Мишель; Vegter, Герт (1996b), "Топологический подметание видимости комплексы через pseudotriangulations", Дискретные и Вычислительная геометрия , 16 (4): 419-453, DOI : 10.1007 / BF02712876 , МР 1414964.
- Поккиола, Мишель; Вегтер, Герт (1996c), «Псевдотриангуляции: теория и приложения» , Труды 12-го ежегодного симпозиума ACM по вычислительной геометрии , стр. 291–300, doi : 10.1145 / 237218.237398.
- Роте, Гюнтер; Сантос, Франциско ; Streinu, Ileana (2003), "Расширяющиеся движения и многогранник заостренных псевдотриангуляций", Дискретная и вычислительная геометрия - The Goodman – Pollack Festschrift , Springer-Verlag, стр. 699–736, arXiv : math.CO/0206027 , doi : 10.1007 / 978-3-642-55566-4_33.
- Роте, Гюнтер; Сантос, Франциско ; Стрейну, Илеана (2008), «Псевдотриангуляции - обзор», Обзоры по дискретной и вычислительной геометрии , Современная математика, 453 , Провиденс, Род-Айленд: Американское математическое общество, стр. 343–410, MR 2405689.
- Роте, Гюнтер; Ван, Цао Ань; Ван, Люшэн; Сюй, Иньфэн (2003), «Об ограниченных минимальных псевдотриангуляциях» (PDF) , Вычисления и комбинаторика , Лекционные заметки по информатике, 2697 , Springer-Verlag, стр. 445–454..
- Спекманн, Беттина ; Toth, Ксаба D. (2005), "Выделение вершин пи-гвардейская в простых многоугольников через псевдо-триангуляции", Дискретные и Вычислительная геометрия , 33 (2): 345-364, DOI : 10.1007 / s00454-004-1091-9 , Руководство по ремонту 2121300.
- Стрейну, Илеана (2000), «Комбинаторный подход к планированию плоских движений руки робота без столкновений» , Труды 41-го ежегодного симпозиума по основам компьютерных наук , IEEE Computer Society, стр. 443–453, doi : 10.1109 / SFCS. 2000,892132.
- Streinu, Илеана (2005), "Псевдо-триангуляция, жесткость и планирование движения", Дискретная и Вычислительная геометрия , 34 (4): 587-635, DOI : 10.1007 / s00454-005-1184-0 , МР 2173930.
- Streinu, Ileana (2006), "Механизмы параллельной перерисовки, псевдотриангуляции и кинетические планарные графы", Proc. Int. Symp. Graph Drawing (GD 2005) , Springer-Verlag, Lecture Notes in Computer Science 3843, стр. 421–433..