1.5. Загальні означення

1. d - вимірним евклідовим простором називається простір d - плексів (x1, x2, ..., xd), що складаються з дійсних чисел x_i (i=1,...,d) з відстанню .
2. Точкою p в просторі E^d називається d - плекс (x₁, x₂, ..., x_d).
   Нехай дано дві різні точки q₁ та q₂. Лінійна комбінація aq₁ + (1 - a)q₂ називається прямою в E^d.
3. Нехай дано дві різні точки q₁ та q₂. Лінійна комбінація aq₁ + (1 - a)q₂ визначає опуклу комбінацію для q₁ та q₂, яка описує прямолінійний відрізок, що сполучає дві точки: q₁ та q₂. Цей відрізок позначають так: .
4. Опуклою оболонкою множини точок S, що належать простору E^d, називається границя найменшої опуклої області в E^d, що охоплює S.
5. Многокутником в просторі E² називається скінчена множина відрізків, в якому кожний кінець відрізка належить рівно двом відрізкам і жодна підмножина відрізків не має вказану властивість. Ці відрізки називаються сторонами (ребрами), а їх кінці - вершинами многокутника.
6. Многокутник називається простим, якщо жодна пара непослідовних його ребер не має спільних точок. Простий многокутник розбиває площину на дві області - внутрішню (скінчену) та зовнішню (нескінченну).
7. Простий многокутник P називається опуклим, якщо його внутрішня область є опуклою множиною.
8. Простий многокутник називається зірковим, якщо існує точка z, не зовнішня для P, така, що для всіх точок p, що належать P, відрізок повністю лежить всередині P. Множина точок z, яка має вказану властивість, називається ядром P. Опуклий многокутник співпадає зі своїм ядром.
9. Граф G = (V, E) називається планарним, якщо його можна покласти на площині без самоперетинів. Прямолінійне укладання ребер планарного графа визначає розбиття площини, яке називається планарним підрозбиттям або картою.
10. Планарне підрозбиття називається тріангуляцією, якщо всі його скінченні грані є трикутниками. Тріангуляцією скінченої множини точок S називається плоский граф S, який має найбільшу можливу кількість ребер.