Зіркоподібний многокутник — многокутна зірчата область на площині. Тобто, вона містить точку, з якої всі точки многокутника видимі.
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOHhMekV4TDFOMFlYSXRhMlZ5Ym1Wc0xuTjJaeTh5TURCd2VDMVRkR0Z5TFd0bGNtNWxiQzV6ZG1jdWNHNW4ucG5n.png)
Формально многокутник P є зіркоподібним, якщо існує така точка z, що для кожної точки p з P відрізок zp цілком лежить у межах P.
Множина усіх точок z з цією властивістю (тобто множина точок, з яких P видно повністю) називається ядром або душею P.
Приклад
Будь-який опуклий многокутник буде зірчастим. Опуклий многокутник є тотожнім зі своїм ядром.
Правильні зірки будуть зіркоподібними, їх центри належать ядру.
Антипаралелограми та [en] з самоперетинами будуть зіркоподібними, ядром буде лише одна точка.
Многокутники видимості є зіркоподібними за визначенням, оскільки кожну точку всередині них повинно бути видно з центру за визначенням.
Алгоритми
Перевірка многокутника на зіркоподібність, і пошук однієї точки ядра, можна виконати за лінійний час, як задачу лінійного програмування з застосуванням методів лінійного програмування для невеликої кількості вимірів (див. http://www.inf.ethz.ch/personal/emo/PublFiles/SubexLinProg_ALG16_96.pdf [ 12 серпня 2017 у Wayback Machine.], стор. 16).
Кожне ребро многокутника визначає внутрішність півплощини, границя якої містить це ребро, а сама півплощина містить внутрішні точки багатокутника, які належать околу внутрішніх точок цього ребра. Ядром многокутника буде перетин усіх внутрішностей півплощин. Перетин довільної множини N півплощин можна знайти за час Θ(N log N) за допомогою методу розділяй та володарюй. Однак, є більш швидкі способи пошуку ядра багатокутника: Лі та Препарата, (1979) розробили алгоритм знаходження ядра за лінійний час.
Примітки
- Франко Препарата, Майкл Шеймос (1985). Computational Geometry – An Introduction. Springer-Verlag. 1st edition: ; 2nd printing, corrected and expanded, 1988: .
- ; Preparata, F. P. (July 1979), , , 26 (3): 415—421, doi:10.1145/322139.322142, архів оригіналу за 24 вересня 2017, процитовано 9 червня 2018