Зіркоподібний многокутник — многокутна область на площині. Тобто, вона містить точку, з якої всі точки многокутника .
![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
Див. також
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет