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

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

В Евклідовій геометрії, псевдотрикутник — це однозв'язна підмножина площини, яка лежить між будь-якими трьома взаємно дотичними опуклими множинами. Псевдотріангуляція — це розбиття області площини на псевдотрикутники, а точна псевдотріангуляція — це псевдотріангуляція, в якій у кожній вершині інцидентні ребра обмежують кут, менший за 180°.

Хоча слова «псевдотрикутник» і «псевдотріангуляція» використовувались з різними значеннями в математиці набагато раніше, терміни, які використовуються тут, були введені в 1993 році Почіолом і Вегтером у зв'язку з обчисленням видимості відносин і бідотичністі, серед опуклих перешкод на площині. Точна псевдотріангуляція вперше була розглянута Ілеаною Штрейну (2000, 2005), у її рішенні до задачі про складаний метр, як доказ того, що будь-яка ламана на площині, може бути випрямлена послідовністю безперервних рухів. Псевдотріангуляція також використовувалася для виявлення зіткнень між рухомими об'єктами, а також для динамічного малювання графів і морфінгу форми. Точна псевдотріангуляція виникає в теорії жорсткості, як приклад мінімально жорстких плоских графів, і в способах розміщення охоронців у теоремі галереї мистецтв. Антиматроїд планарного графа множини точок призводить до точної псевдотріангуляції, попре те, що не всі точні псевдотріангуляції можуть виникнути в цьому випадку.

Для детального огляду великої частини розглянутого матеріалу, див. Роут, Сантос та Штрейну (2008).

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

Почіола і Вегтер (1996) спочатку визначили псевдотрикутник як однозв'язну область площини, обмежену трьома гладкими опуклими кривими, які дотичні до їх кінців. Проте подальші роботи зупинилися на ширшому визначенні, яке застосовується до загальних багатокутників, а також в областях, обмежених гладкими кривими, і кутів, відмінних від нуля, в трьох вершинах. У цьому широкому визначенні, псевдотрикутник є однозв'язною областю площини, що має три опуклі вершини, тобто, кожна вершина охоплює внутрішній кут менший за 180°. Три граничні криві, що з'єднують ці вершини, повинні бути опуклими, в тому сенсі, що будь-який відрізок, що з'єднує дві точки на одній граничній кривій, повинен лежати або цілком поза, або на межі псевдотрикутника. Таким чином, псевдотрикутник — це область між опуклою оболонкою цих трьох кривих, а в більш загальному сенсі — будь-які три попарно дотичні опуклі множини утворюють псевдотрикутник, який лежить між ними.

При створенні алгоритмів особливий інтерес становить опис псевдотрикутників, які є багатокутниками. В багатокутнику, вершина є опуклою, якщо вона охоплює внутрішній кут менший за 180°, а в іншому випадку, увігнутою (зокрема, ми кут, який дорівнює 180° увігнутим). Будь-який многокутник повинен мати принаймні три опуклі кути, оскільки загальний зовнішній кут багатокутника дорівнює 2π, а внесок у цю суму кожного опуклого кута менший, ніж π, а відповідно увігнуті кути мають нульовий або від'ємний внесок. Багатокутний псевдотрикутник — це багатокутник, який має рівно три опуклі вершини. Зокрема, будь-який трикутник, і будь-який неопуклий чотирикутник, є псевдотрикутником.

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

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

Псевдотріангуляція — це розбиття області на площині на псевдотрикутники. Будь-яка тріангуляція області на площині є псевдотріангуляцією. У той час коли будь-які дві тріангуляції однієї й тієї ж області повинні мати однакове число ребер і трикутників, те ж саме можна сказати про псевдотріангуляцію; наприклад, якщо сама область є n -вершинним багатокутним псевдотрикутником, то псевдотріангуляція може мати, як один псевдотрикутник, так і n трикутників, n − 2 псевдотрикутників та 2n − 3 ребра.

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

Агарвал і ін. (2002) описують структури даних для підтримки псевдотріангуляції рухомих точок або рухомих багатокутників. Вони показують, що використання псевдотріангуляції замість тріангуляції дозволяє створити алгоритми для підтримки цих структур, з відносно невеликою кількістю комбінаторних змін, і вони використовують ці динамічні псевдотріангуляції для виявлення зіткнень між рухомими об'єктами.

Гудмундссон і ін. (2004) розглядають задачу знаходження псевдотріангуляції множини точок, або багатокутника з загальною мінімальною довжиною ребер, і пропонують алгоритми апроксимації для цієї задачі.

Точна псевдотріангуляція

Послідовність відсікання віл планарної множини точок та точна псевдотриангуляція, яка виникає з такої послідовності.

Точна псевдотриангуляція може бути визначена як скінченна множина відрізків, які не перетинаються, і в кожній вершині інцидентні їй відрізки охоплюють кут, який не перевищує π, й неможливо додати відрізок між будь-якими двома вершинами, так, щоб не порушити цю властивість. Не важко побачити, що точна псевдотріангуляція є псевдотріангуляцією її опуклої оболонки: всі ребра опуклої оболонки можуть бути додані при збереженні властивості охоплення кута, і всі внутрішні грані повинні бути псевдотрикутниками, інакше можна буде з'єднати дві вершини бідотичним відрізком.

Точна псевдотріангуляція з v вершинами повинна мати рівно 2v − 3 ребер. Це випливає з простого подвійного обрахунку за допомогою характеристики Ейлера: оскільки кожна грань, зовнішнього псевдотрикутника має три опуклі кути, псевдотріангуляція повинна мати 3f − 3 опуклі кути між суміжними ребрами. Кожне ребро розташоване за годинниковою стрілкою ребер для двох кутів, так що в цілому буде 2e кутів, з яких всі, крім v є опуклими. Таким чином, 3f − 3 = 2e − v. Поєднання з рівнянням Ейлера f − e + v = 2 результату рішення системи лінійних алгебраїчних рівнянь дає результат e = 2v − 3. Також, можна визначити, що f = v − 1 (включаючи опуклу оболонку як одну з граней), тому псевдотриангуляція повинна мати рівно v − 2 псевдотрикутників.

Точно так само, як будь-яка k-вершина підграфу точної псевдотріангуляції може бути завершена, щоб сформувати точну псевдотріангуляцію його вершин, підграф повинен мати не більше ніж 2k − 3 ребер. Таким чином, точні псевдотріангуляції задовольняють умовам і визначають граф Ламана, якщо вони мають в точності 2v − 3 ребер, а їх k-вершинні підграфи мають не більше ніж 2k − 3 ребер. Графи Ламана, а також точні псевдотріангуляції, є мінімально жорсткими графами у розмірності два. Кожен плоский граф Ламана може бути побудований у вигляді точної псевдотріангуляції, хоча не кожне планарне відображення плоского графа Ламана є псевдотріангуляцією.

Інший спосіб знаходження точної псевдотріангуляції є відсікання (англ. shell) множини точок; тобто, видалення вершин опуклої оболонки вершин, одна за одною, поки всі вершини не будуть видалені. Сімейства послідовностей видалених точок, які можуть бути сформовані у такий спосіб називають послідовністю відсікання (англ. shelling sequence) множини точок, і множина ребер опуклих оболонок, які утворюються цим процесом видалення, у підсумку дають псевдотріангуляцію. Однак, не все вказує, що точні псевдотріангуляції можуть бути утворені в такий спосіб.

Аіхолзер та ін. (2004) показують, що множина з n точок, h з яких належать до опуклої оболонки множини, повинні мати щонайменше, C_h−2×3^{n − h} різних точних псевдотріангуляцій, де C_i позначає i-те число Каталана. Як наслідок, вони показують, що множина точок з найменшою кількістю точних псевдотріангуляцій — це набір вершин опуклих багатокутників. Аіхолзер і ін. (2006) досліджували множини точок з великою кількістю точних псевдотріангуляцій. Науковці та дослідники в галузі геометрії також створили алгоритми для перерахування всіх точних псевдотріангуляцій множини точок з невеликим часом на виконання псевдотріангуляції.

Див. також

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

Посилання

• Agarwal, Pankaj K.; Basch, Julien; Guibas, Leonidas J.; Hershberger, John; Zhang, Li (2002), Deformable free-space tilings for kinetic collision detection, International Journal of Robotics Research, 21 (3): 179—197, doi:10.1177/027836402320556395.
• Aichholzer, Oswin; Aurenhammer, Franz; Krasser, Hannes; Speckmann, Bettina (2004), Convexity minimizes pseudo-triangulations, Computational Geometry Theory and Applications, 28 (1): 3—10, doi:10.1016/j.comgeo.2004.01.002, MR 2070708. Preliminary version in Canad. Conf. Comput. Geom., 2002.
• Aichholzer, Oswin; Orden, David; Santos, Francisco; Speckmann, Bettina (2008), On the number of pseudo-triangulations of certain point sets, Journal of Combinatorial Theory, Series A, 115 (2): 254—278, arXiv:math/0601747, doi:10.1016/j.jcta.2007.06.002, MR 2382515
• Bereg, Sergey (2005), Enumerating pseudo-triangulations in the plane, Computational Geometry Theory and Applications, 30 (3): 207—222, doi:10.1016/j.comgeo.2004.09.002, MR 2123970.
• Brönnimann, Hervé; Kettner, Lutz; Pocchiola, Michel; Snoeyink, Jack (2006), Counting and enumerating pointed pseudotriangulations with the greedy flip algorithm, SIAM Journal on Computing, 36 (3): 721—739, doi:10.1137/050631008, MR 2263009.
• Gudmundsson, Joachim; Levcopoulos, Christos; Kamal, Lodaya; Meena, Mahajan (2004), Minimum weight pseudo-triangulations (PDF), у Lodaya, Kamal; Mahajan, Meena (ред.), FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science, т. 3328, Springer-Verlag, с. 299—310, arXiv:0705.3888, doi:10.1007/b104325, ISBN 978-3-540-24058-7.
• Haas, Ruth; Orden, David; Rote, Günter; Santos, Francisco; Servatius, Brigitte; Servatius, Herman; Souvaine, Diane; Streinu, Ileana; Whiteley, Walter (2005), Planar minimally rigid graphs and pseudo-triangulations, Computational Geometry Theory and Applications, 31 (1–2): 31—61, arXiv:math/0307347, doi:10.1016/j.comgeo.2004.07.003, MR 2131802.
• Har-Peled, Sariel (2002), A comment on pseudo-triangulation in three dimensions, архів оригіналу за 12 вересня 2006, процитовано 12 квітня 2007.
• Pocchiola, Michel; Vegter, Gert (1996a), The visibility complex, International Journal of Computational Geometry and Applications, 6 (3): 297—308, doi:10.1142/S0218195996000204, архів оригіналу за 3 грудня 2006. Preliminary version in Ninth ACM Symp. Computational Geometry (1993) 328—337.
• Pocchiola, Michel; Vegter, Gert (1996b), Topologically sweeping visibility complexes via pseudotriangulations, Discrete and Computational Geometry, 16 (4): 419—453, doi:10.1007/BF02712876, MR 1414964.
• Pocchiola, Michel; Vegter, Gert (1996c), Pseudo-triangulations: theory and applications, Proceedings of the 12th Annual ACM Symposium on Computational Geometry, с. 291—300, doi:10.1145/237218.237398.
• Rote, Günter; Santos, Francisco; Streinu, Ileana (2003), Expansive motions and the polytope of pointed pseudo-triangulations, Discrete and Computational Geometry — The Goodman–Pollack Festschrift, Springer-Verlag, с. 699—736, arXiv:math.CO/0206027, doi:10.1007/978-3-642-55566-4_33.
• Rote, Günter; Santos, Francisco; Streinu, Ileana (2008), Pseudo-triangulations — a survey, Surveys on discrete and computational geometry, Contemporary Mathematics, т. 453, Providence, RI: American Mathematical Society, с. 343—410, MR 2405689.
• Rote, Günter; Wang, Cao An; Wang, Lusheng; Xu, Yinfeng (2003), On constrained minimum pseudotriangulations (PDF), Computing and Combinatorics, Lecture Notes in Computer Science, т. 2697, Springer-Verlag, с. 445—454.
• Speckmann, Bettina; Tóth, Csaba D. (2005), Allocating vertex π-Guards in simple polygons via pseudo-triangulations, Discrete and Computational Geometry, 33 (2): 345—364, doi:10.1007/s00454-004-1091-9, MR 2121300.
• Streinu, Ileana (2000), A combinatorial approach to planar non-colliding robot arm motion planning, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, IEEE Computer Society, с. 443—453, doi:10.1109/SFCS.2000.892132.
• Streinu, Ileana (2005), Pseudo-triangulations, rigidity and motion planning, Discrete and Computational Geometry, 34 (4): 587—635, doi:10.1007/s00454-005-1184-0, MR 2173930.
• Streinu, Ileana (2006), Parallel-redrawing mechanisms, pseudo-triangulations and kinetic planar graphs, Proc. Int. Symp. Graph Drawing (GD 2005), Springer-Verlag, Lecture Notes in Computer Science 3843, с. 421—433.