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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. такожРедагувати

ПриміткиРедагувати

  1. Для «псевдотрикутник» дивись, наприклад Джон Генрі Константайн Вайтгед (1961). Колектори з поперечними полями в евклідовому просторі. Літописи математики[en] 73 (1): 154–212. JSTOR 1970286. MR 0124917. doi:10.2307/1970286. . Сторінка 196 в цій статті посилається до «стану псевдотрикутник» у функціональному наближенні. Для «псевдотріангуляції» дивись, наприклад Белага, Є.Г (1976). роботі Хівуда вектори псевдотріангуляції. Доповіді академії наук СРСР[en] (Russian) 231 (1): 14–17. MR 0447029. .
  2. Агарвал (2002).
  3. Стрейну (2006).
  4. Хаас (2005)
  5. Спекмен і Тосс (2005).
  6. Хар-Пеллед(2002).
  7. Rote, Wang, Wang, and Xu (2003), Теорема 4 і Фігура 4.
  8. Вперше відкрито вченим Стрейну (2000), але аргумент, який ми наводимо тут, від Хааса та ін. (2005), Лема 5.
  9. Хаас і ін. (2005).
  10. Берег (2005); Бренніман та ін. (2006).

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