Зіркоподібний многокутник

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Зірчастий многокутник (вгорі). Його ядро зображено знизу червоним кольором.

Зіркоподібний многокутник — многокутна зірчата область на площині. Тобто, вона містить точку, з якої всі точки многокутника видимі.

Формально многокутник P є зіркоподібним, якщо існує така точка z, що для кожної точки p з P відрізок zp цілком лежить у межах P.[1]

Множина усіх точок z з цією властивістю (тобто множина точок, з яких P видно повністю) називається ядром або душею P.

Приклад[ред. | ред. код]

Будь-який опуклий многокутник буде зірчастим. Опуклий многокутник є тотожнім зі своїм ядром.

Правильні зірки будуть зіркоподібними, їх центри належать ядру.

Антипаралелограми та шестикутники Лемуана[en] з самоперетинами будуть зіркоподібними, ядром буде лише одна точка.

Многокутники видимості є зіркоподібними за визначенням, оскільки кожну точку всередині них повинно бути видно з центру за визначенням.

Алгоритми[ред. | ред. код]

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

Кожне ребро многокутника визначає внутрішність півплощини, границя якої містить це ребро, а сама півплощина містить внутрішні точки багатокутника, які належать околу внутрішніх точок цього ребра. Ядром многокутника буде перетин усіх внутрішностей півплощин. Перетин довільної множини N півплощин можна знайти за час Θ(N log N), якщо використати підхід розділяй та володарюй.[1] Однак, є більш швидкі способи пошуку ядра багатокутника: Лі та Препарата, (1979)[2] розробили алгоритм знаходження ядра за лінійний час.

Примітки[ред. | ред. код]

  1. а б Франко Препарата, Майкл Шеймос (1985). Computational Geometry – An Introduction. Springer-Verlag. 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3. 
  2. Lee, D. T.; Preparata, F. P. (July 1979). An Optimal Algorithm for Finding the Kernel of a Polygon. Journal of the ACM 26 (3): 415–421. doi:10.1145/322139.322142. 

Див. також[ред. | ред. код]