Зіркоподібний многокутник: відмінності між версіями

Перевірка многокутника на зіркоподібність, і пошук однієї точки ядра, можна зробитивиконати за [[Часова складність алгоритму|лінійний час]], як задачу [[Лінійне програмування|лінійного програмування]] з застосуванням методів лінійного програмування для невеликої кількості вимірів (див. http://www.inf.ethz.ch/personal/emo/PublFiles/SubexLinProg_ALG16_96.pdf, стор. 16).

Кожне ребро многокутника визначає внутрішність [[Півпростір|півплощини]], границя якої містить це ребро, а сама півплощина містить внутрішні точки багатокутника, які належать [[Окіл|околу]] внутрішніх точок цього ребра. Ядром многокутника буде перетин усіх внутрішностей півплощин. Перетин довільної множини ''N'' півплощин можна знайти за час [[Нотація Ландау|Θ]](''N'' log ''N''), якщоза використатидопомогою підхідметоду [[Розділяй та володарюй (інформатика)|розділяй та володарюй]].<ref name=PS/> Однак, є більш швидкі способи пошуку ядра багатокутника: