Плаский прямолінійний граф (ППЛГ) — це термін використовуваний в обчислювальній геометрії для вкладення планарного графу на площині так, що його ребра переходять у прямолінійні відрізки.Теорема Фарі (1948) стверджує, що кожний планарний граф має такий тип вкладення.
В обчислювальній геометрії ППЛГ часто називають пласким розбиттям, з припущенням або ствердженням, що розбиття полігональне. Максимальним пласким розбиттям називають таке розбиття, що неможливо додати жодне ребро, яке б поєднувало дві вершини, так щоб не порушити пласкість.
ППЛГ без вершин степені 1 визначає розбиття площини на полігональні регіони і навпаки. Відсутність вершин степені 1 спрощує опис багатьох алгоритмів, але це не суттєво.
ППЛГ може слугувати як представлення різноманітних мап. Наприклад, географічна карта в геоінформаційній системі.
Особливим випадком ППЛГ є тріангуляції: тріангуляція багатокутника, Тріангуляція множини точок. Багатоточкова тріангуляція є максимальною ППЛГ в тому сенсі, що неможливо додати до них прямолінійні ребра, так щоб граф залишився планарним. Тріангуляції мають численні застосування в різних областях.
ППЛГ може розглядатися як особливий вид [en]. Однак в дискусіях, пов'язаних з евклідовими графами основний інтерес представляє їх метричні властивості, тобто, відстані між вершинами, в той час як для ППЛГ основний інтерес пов'язаний з топологічними властивостями. Для деяких графів, таких як тріангуляція Делоне, як метричні, так і топологічні властивості мають важливе значення.
Задачі в термінах ППЛГ
- Локалізація точки. Для певної точки, знайти якій грані ППЛГ вона належить.
- . Знайти накладення двох ППЛГ (карт), що є розбиттям площини одночасно двома ППЛГ.
Див. також
- Подвійно зв'язаний список ребер, структура даних для ППЛГ
Примітки
- Препарата і Шеймос (1985). Обчислювальна геометрія - Вступ. Springer-Verlag. 1-е видання: ; 2-й випуск, виправлений і розширений, 1988: ;.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Plaskij pryamolinijnij graf PPLG ce termin vikoristovuvanij v obchislyuvalnij geometriyi dlya vkladennya planarnogo grafu na ploshini tak sho jogo rebra perehodyat u pryamolinijni vidrizki Teorema Fari 1948 stverdzhuye sho kozhnij planarnij graf maye takij tip vkladennya Priklad planarnogo pryamolinijnogo grafu V obchislyuvalnij geometriyi PPLG chasto nazivayut plaskim rozbittyam z pripushennyam abo stverdzhennyam sho rozbittya poligonalne Maksimalnim plaskim rozbittyam nazivayut take rozbittya sho nemozhlivo dodati zhodne rebro yake b poyednuvalo dvi vershini tak shob ne porushiti plaskist PPLG bez vershin stepeni 1 viznachaye rozbittya ploshini na poligonalni regioni i navpaki Vidsutnist vershin stepeni 1 sproshuye opis bagatoh algoritmiv ale ce ne suttyevo PPLG mozhe sluguvati yak predstavlennya riznomanitnih map Napriklad geografichna karta v geoinformacijnij sistemi Osoblivim vipadkom PPLG ye triangulyaciyi triangulyaciya bagatokutnika Triangulyaciya mnozhini tochok Bagatotochkova triangulyaciya ye maksimalnoyu PPLG v tomu sensi sho nemozhlivo dodati do nih pryamolinijni rebra tak shob graf zalishivsya planarnim Triangulyaciyi mayut chislenni zastosuvannya v riznih oblastyah PPLG mozhe rozglyadatisya yak osoblivij vid en Odnak v diskusiyah pov yazanih z evklidovimi grafami osnovnij interes predstavlyaye yih metrichni vlastivosti tobto vidstani mizh vershinami v toj chas yak dlya PPLG osnovnij interes pov yazanij z topologichnimi vlastivostyami Dlya deyakih grafiv takih yak triangulyaciya Delone yak metrichni tak i topologichni vlastivosti mayut vazhlive znachennya Zadachi v terminah PPLGLokalizaciya tochki Dlya pevnoyi tochki znajti yakij grani PPLG vona nalezhit Znajti nakladennya dvoh PPLG kart sho ye rozbittyam ploshini odnochasno dvoma PPLG Div takozhPodvijno zv yazanij spisok reber struktura danih dlya PPLGPrimitkiPreparata i Shejmos 1985 Obchislyuvalna geometriya Vstup Springer Verlag 1 e vidannya ISBN 0 387 96131 3 2 j vipusk vipravlenij i rozshirenij 1988 ISBN 3 540 96131 3