Плоский прямолінійний граф
Плаский прямолінійний граф (ППЛГ) — це термін використовуваний в обчислювальній геометрії для вкладення планарного графу на площині так, що його ребра переходять у прямолінійні відрізки.[1] Теорема Фарі (1948) стверджує, що кожний планарний граф має такий тип вкладення.
В обчислювальній геометрії ППЛГ часто називають пласким розбиттям, з припущенням або ствердженням, що розбиття полігональне. Максимальним пласким розбиттям називають таке розбиття, що неможливо додати жодне ребро, яке б поєднувало дві вершини, так щоб не порушити пласкість.
ППЛГ без вершин степені 1 визначає розбиття площини на полігональні регіони і навпаки. Відсутність вершин степені 1 спрощує опис багатьох алгоритмів, але це не суттєво.
ППЛГ може слугувати як представлення різноманітних мап. Наприклад, географічна карта в геоінформаційній системі.
Особливим випадком ППЛГ є тріангуляції: тріангуляція багатокутника, Тріангуляція множини точок. Багатоточкова тріангуляція є максимальною ППЛГ в тому сенсі, що неможливо додати до них прямолінійні ребра, так щоб граф залишився планарним. Тріангуляції мають численні застосування в різних областях.
ППЛГ може розглядатися як особливий вид евклідових графів[en]. Однак в дискусіях, пов'язаних з евклідовими графами основний інтерес представляє їх метричні властивості, тобто, відстані між вершинами, в той час як для ППЛГ основний інтерес пов'язаний з топологічними властивостями. Для деяких графів, таких як тріангуляція Делоне, як метричні, так і топологічні властивості мають важливе значення.
Задачі в термінах ППЛГ[ред. | ред. код]
- Локалізація точки. Для певної точки, знайти якій грані ППЛГ вона належить.
- Накладення карт. Знайти накладення двох ППЛГ (карт), що є розбиттям площини одночасно двома ППЛГ.
Див. також[ред. | ред. код]
- Подвійно зв'язаний список ребер, структура даних для ППЛГ
Примітки[ред. | ред. код]
- ↑ Препарата і Шеймос (1985). Обчислювальна геометрія - Вступ. Springer-Verlag. 1-е видання: ISBN 0-387-96131-3; 2-й випуск, виправлений і розширений, 1988: ISBN 3-540-96131-3;.