Псевдотреугольник - Pseudotriangle
В Евклидова плоская геометрия, а псевдотреугольник (псевдотреугольник) это односвязный подмножество самолет который лежит между любыми тремя взаимно касающимися выпуклые множества. А псевдотриангуляция (псевдотриангуляции) представляет собой разбиение части плоскости на псевдотреугольники, а точечная псевдотриангуляция является псевдотриангуляцией, в которой в каждой вершине инцидентные ребра перекрывают угол меньше π.
Хотя слова «псевдотреугольник» и «псевдотриангуляция» использовались в математике в различных значениях гораздо дольше,[1] используемые здесь термины были введены в 1993 году Мишелем Поккиолой и Гертом Вегтером в связи с вычислением отношений видимости и битангенты среди выпуклых препятствий на плоскости. Остроконечные псевдотриангуляции впервые были рассмотрены Илеана Стрейну (2000, 2005) как часть ее решения проблема плотника с линейкой, доказательство того, что любой простой многоугольный путь в плоскости можно выпрямить последовательностью непрерывных движений. Псевдотриангуляции также использовались для обнаружения столкновений между движущимися объектами.[2] и для динамического рисования графиков и преобразования форм.[3] Остроконечные псевдотриангуляции возникают в теория жесткости как примеры минимально жестких планарные графы,[4] и в методах размещения охранников в связи с Теорема о художественной галерее.[5] В обстрел антиматроида плоского множества точек порождает точечные псевдотриангуляции,[6] хотя не все остроконечные псевдотриангуляции могут возникать таким образом.
Для подробного обзора большей части обсуждаемого здесь материала см. Rote, Сантос, и Streinu (2008).
Псевдотреугольники
Поккиола и Вегтер (1996a, b, c) первоначально определили псевдотреугольник как односвязную область на плоскости, ограниченную тремя гладкими выпуклыми кривыми, которые касаются своих концов. Однако последующая работа остановилась на более широком определении, которое в более общем смысле применимо к полигоны а также в области, ограниченные гладкими кривыми, что допускает ненулевые углы в трех вершинах. В этом более широком определении псевдотреугольник - это односвязная область плоскости, имеющая три выпуклые вершины. Три граничные кривые, соединяющие эти три вершины, должны быть выпуклыми в том смысле, что любой отрезок прямой, соединяющий две точки на одной и той же граничной кривой, должен полностью лежать за пределами или на границе псевдотреугольника. Таким образом, псевдотреугольник - это область между выпуклыми оболочками этих трех кривых, и в более общем случае любые три взаимно касательные выпуклые множества образуют псевдотреугольник, который лежит между ними.
Для алгоритмических приложений особый интерес представляет характеризация псевдотреугольников, которые являются многоугольниками. В многоугольнике вершина выпуклый если он охватывает внутренний угол меньше π, и вогнутый в противном случае (в частности, мы считаем вогнутым угол ровно π). Любой многоугольник должен иметь по крайней мере три выпуклых угла, потому что общий внешний угол многоугольника равен 2π, каждый из выпуклых углов дает меньше π, а вклад вогнутых углов равен нулю или отрицательному значению. Многоугольный псевдотреугольник - это многоугольник, имеющий ровно три выпуклые вершины. В частности, любые треугольник, и любые невыпуклые четырехугольник, является псевдотреугольником.
В выпуклый корпус любого псевдотреугольника есть треугольник. Кривые вдоль границы псевдотреугольника между каждой парой выпуклых вершин либо лежат внутри треугольника, либо совпадают с одним из его ребер.
Псевдотриангуляции
А псевдотриангуляция представляет собой разбиение области плоскости на псевдотреугольники. Любой триангуляция области плоскости - псевдотриангуляция. В то время как любые две триангуляции одной и той же области должны иметь одинаковое количество ребер и треугольников, то же самое нельзя сказать о псевдотриангуляциях; например, если регион сам является п-вершинный многоугольник псевдотреугольник, то его псевдотриангуляция может иметь всего один псевдотреугольник и п краев, или столько, сколько п - 2 псевдотреугольника и 2п - 3 ребра.
А минимальная псевдотриангуляция это псевдотриангуляция Т такой, что нет подграфа Т - псевдотриангуляция, покрывающая ту же выпуклую область плоскости. Минимальная псевдотриангуляция с п вершины должны иметь не менее 2п - 3 ребра; если в нем ровно 2п - 3 ребра, это должна быть точечная псевдотриангуляция, но существуют минимальные псевдотриангуляции с 3п - O (1) ребер.[7]
Agarwal et al. (2002) описывают структуры данных для поддержки псевдотриангуляций движущихся точек или движущихся полигонов. Они показывают, что использование псевдотриангуляций вместо триангуляций позволяет их алгоритмам поддерживать эти структуры с относительно небольшими комбинаторными изменениями при перемещении входных данных, и они используют эти динамические псевдотриангуляции для обнаружения столкновений между движущимися объектами.
Gudmundsson et al. (2004) рассматривают проблему поиска псевдотриангуляции набора точек или многоугольника с минимальной общей длиной ребра и предоставляют алгоритмы аппроксимации для этой задачи.
Остроконечные псевдотриангуляции
А точечная псевдотриангуляция может быть определен как конечный непересекающийся набор линейных сегментов, такой, что в каждой вершине инцидентные линейные сегменты охватывают угол не более π, и такой, что никакие линейные сегменты не могут быть добавлены между любыми двумя существующими вершинами при сохранении этого свойства. Нетрудно видеть, что остроконечная псевдотриангуляция является псевдотриангуляцией ее выпуклой оболочки: все выпуклые края оболочки могут быть добавлены с сохранением свойства перекрытия углов, а все внутренние грани должны быть псевдотреугольниками, иначе a битангентный отрезок можно добавить между двумя вершинами лица.
Остроконечная псевдотриангуляция с v вершин должно быть ровно 2v - 3 ребра.[8] Это следует простой двойной счет аргумент, связанный с Эйлерова характеристика: поскольку каждая грань, кроме внешней, представляет собой псевдотреугольник с тремя выпуклыми углами, псевдотриангуляция должна иметь 3ж - 3 выпуклых угла между смежными краями. Каждое ребро является ребром по часовой стрелке для двух углов, так что всего получается 2е углы, из которых все, кроме v выпуклые. Таким образом, 3ж − 3 = 2е − v. Объединяя это с уравнением Эйлера ж − е + v = 2 и решив полученный совместные линейные уравнения дает е = 2v - 3. Тот же аргумент также показывает, что ж = v - 1 (включая выпуклую оболочку в качестве одной из граней), поэтому псевдотриангуляция должна иметь ровно v - 2 псевдотреугольника.
Аналогично, поскольку любой k-вершинный подграф заостренной псевдотриангуляции может быть дополнен заостренной псевдотриангуляцией его вершин, подграф должен иметь не более 2k - 3 ребра. Таким образом, точечные псевдотриангуляции удовлетворяют условиям, определяющим Графы Ламана: у них ровно 2v - 3 ребра, и их k-вершинных подграфов не более 2k - 3 ребра. Графы Ламана и, следовательно, также заостренные псевдотриангуляции, являются минимально жесткими графами в двух измерениях. Каждый плоский граф Ламана может быть нарисован как точечная псевдотриангуляция, хотя не каждый планарный рисунок плоского графа Ламана является псевдотриангуляцией.[9]
Другой способ найти остроконечную псевдотриангуляцию - это ракушка набор точек; то есть удалять вершины выпуклой оболочки одну за другой, пока не будут удалены все точки. Семейство последовательностей удалений, которые могут быть сформированы таким образом, - это обстрел антиматроида набора точек, а набор ребер выпуклых оболочек последовательности наборов точек, сформированных этим процессом удаления, образует псевдотриангуляцию.[6] Однако не все точечные псевдотриангуляции могут быть сформированы таким образом.
Aichholzer et al. (2004) показывают, что набор п точки, час из которых принадлежат выпуклый корпус комплекта должно быть не менее Cчас−2×3п−час разные точечные псевдотриангуляции, где Cя обозначает яth Каталонский номер. Как следствие, они показывают, что множества точек с наименьшим количеством заостренных псевдотриангуляций являются наборами вершин выпуклых многоугольников. Aichholzer et al. (2006) исследуют точечные множества с большим количеством заостренных псевдотриангуляций. Исследователи вычислительной геометрии также предоставили алгоритмы для перечисления всех точечных псевдотриангуляций набора точек за небольшой промежуток времени для каждой псевдотриангуляции.[10]
Смотрите также
Примечания
- ^ В отношении «псевдотреугольника» см., Например, Уайтхед, Дж. Х. С. (1961), «Многообразия с поперечными полями в евклидовом пространстве», Анналы математики, 73 (1): 154–212, Дои:10.2307/1970286, JSTOR 1970286, Г-Н 0124917.На стр. 196 эта статья ссылается на «условие псевдотреугольника» в функциональном приближении. Для «псевдотриангуляции» см., Например, Белага, È. G. (1976), "[Векторы Хивуда псевдотриангуляций]", Доклады Академии Наук СССР (по-русски), 231 (1): 14–17, Г-Н 0447029.
- ^ Agarwal et al. (2002).
- ^ Стрейну (2006).
- ^ Haas et al. (2005)
- ^ Спекманн и Тот (2005).
- ^ а б Хар-Пелед (2002).
- ^ Роте, Ван, Ван и Сюй (2003), теорема 4 и рисунок 4.
- ^ Впервые показано Стрейну (2000), но приведенные здесь аргументы взяты из Haas et al. (2005), лемма 5.
- ^ Haas et al. (2005).
- ^ Берег (2005); Brönnimann et al. (2006).
Рекомендации
- Агарвал, Панкадж К.; Баш, Жюльен; Гибас, Леонидас Дж.; Хершбергер, Джон; Чжан, Ли (2002), "Деформируемые мозаики в свободном пространстве для кинетического обнаружения столкновений", Международный журнал исследований робототехники, 21 (3): 179–197, Дои:10.1177/027836402320556395.
- Айхольцер, Освин; Ауренхаммер, Франц; Крассер, Ханнес; Спекманн, Беттина (2004), «Выпуклость минимизирует псевдотриангуляции», Теория вычислительной геометрии и приложения, 28 (1): 3–10, Дои:10.1016 / j.comgeo.2004.01.002, Г-Н 2070708. Предварительная версия в Канаде. Конф. Comput. Геом., 2002.
- Айхольцер, Освин; Орден, Дэвид; Сантос, Франциско; Спекманн, Беттина (2008), «О количестве псевдотриангуляций некоторых точечных множеств», Журнал комбинаторной теории, серия А, 115 (2): 254–278, arXiv:математика / 0601747, Дои:10.1016 / j.jcta.2007.06.002, Г-Н 2382515
- Берег, Сергей (2005), "Перечисление псевдотриангуляций на плоскости", Теория вычислительной геометрии и приложения, 30 (3): 207–222, Дои:10.1016 / j.comgeo.2004.09.002, Г-Н 2123970.
- Брённиманн, Эрве; Кеттнер, Лутц; Поккиола, Мишель; Snoeyink, Джек (2006), "Подсчет и перечисление точечных псевдотриангуляций с помощью алгоритма жадного переворота", SIAM Журнал по вычислениям, 36 (3): 721–739, Дои:10.1137/050631008, Г-Н 2263009.
- Гудмундссон, Иоахим; Левкопулос, Христос; Камаль, Лодая; Мина, Махаджан (2004), «Псевдотриангуляции минимального веса» (PDF)в Лодая, Камаль; Махаджан, Мина (ред.), FSTTCS 2004: Основы программных технологий и теоретической информатики, Конспект лекций по информатике, 3328, Springer-Verlag, стр. 299–310, arXiv:0705.3888, Дои:10.1007 / b104325, ISBN 978-3-540-24058-7.
- Хаас, Рут; Орден, Дэвид; Роте, Гюнтер; Сантос, Франциско; Серватиус, Бриджит; Серватий, Герман; Сувейн, Дайан; Стрейну, Илеана; Уайтли, Уолтер (2005), «Плоские минимально жесткие графы и псевдотриангуляции», Теория вычислительной геометрии и приложения, 31 (1–2): 31–61, arXiv:математика / 0307347, Дои:10.1016 / j.comgeo.2004.07.003, Г-Н 2131802.
- Хар-Пелед, Сариэль (2002), Комментарий к псевдотриангуляции в трех измерениях, заархивировано из оригинал на 2006-09-12, получено 2007-04-12.
- Поккиола, Мишель; Вегтер, Герт (1996a), «Комплекс видимости», Международный журнал вычислительной геометрии и приложений, 6 (3): 297–308, Дои:10.1142 / S0218195996000204, заархивировано из оригинал на 2006-12-03. Предварительная версия в Девятый симпозиум ACM. Вычислительная геометрия (1993) 328–337.
- Поккиола, Мишель; Вегтер, Герт (1996b), "Топологически широкие комплексы видимости через псевдотриангуляции", Дискретная и вычислительная геометрия, 16 (4): 419–453, Дои:10.1007 / BF02712876, Г-Н 1414964.
- Поккиола, Мишель; Вегтер, Герт (1996c), «Псевдотриангуляции: теория и приложения», Материалы 12-го ежегодного симпозиума ACM по вычислительной геометрии, стр. 291–300, Дои:10.1145/237218.237398.
- Роте, Гюнтер; Сантос, Франциско; Стрейну, Илеана (2003), «Расширяющиеся движения и многогранник точечных псевдотриангуляций», Дискретная и вычислительная геометрия - Festschrift Гудмана – Поллака, Springer-Verlag, стр. 699–736, arXiv:math.CO/0206027, Дои:10.1007/978-3-642-55566-4_33.
- Роте, Гюнтер; Сантос, Франциско; Стрейну, Илеана (2008), «Псевдотриангуляции - обзор», Обзоры по дискретной и вычислительной геометрии, Современная математика, 453, Провиденс, Род-Айленд: Американское математическое общество, стр. 343–410, Г-Н 2405689.
- Роте, Гюнтер; Ван, Цао Ань; Ван, Люшэн; Сюй, Иньфэн (2003), «О минимальных условных псевдотриангуляциях» (PDF), Вычислительная техника и комбинаторика, Конспект лекций по информатике, 2697, Springer-Verlag, стр. 445–454..
- Спекманн, Беттина; Тот, Чаба Д. (2005), "Размещение π-охранников вершин в простых многоугольниках с помощью псевдотриангуляций", Дискретная и вычислительная геометрия, 33 (2): 345–364, Дои:10.1007 / s00454-004-1091-9, Г-Н 2121300.
- Стрейну, Илеана (2000), «Комбинаторный подход к планированию плоских движений руки робота без столкновений», Материалы 41-го ежегодного симпозиума по основам информатики, IEEE Computer Society, стр. 443–453, Дои:10.1109 / SFCS.2000.892132.
- Стрейну, Илеана (2005), «Псевдотриангуляции, жесткость и планирование движения», Дискретная и вычислительная геометрия, 34 (4): 587–635, Дои:10.1007 / s00454-005-1184-0, Г-Н 2173930.
- Стрейну, Илеана (2006), «Механизмы параллельной перерисовки, псевдотриангуляции и кинетические планарные графы», Proc. Int. Symp. Графический рисунок (GD 2005), Springer-Verlag, Lecture Notes in Computer Science 3843, pp. 421–433..