Звездообразный многоугольник

Многоугольник в форме звезды (вверху). Его ядро показано внизу красным цветом.

В геометрии звездообразный многоугольник — это многоугольная область на плоскости, представляющая собой звездную область , то есть многоугольник, содержащий точку, из которой видна вся граница многоугольника .

Формально многоугольник $P$ является звездообразным, если существует точка $z$ такая, что для каждой точки $p$ из $P$ отрезок ${\overline {zp}}$ лежит внутри $P.$ полностью ^[1] Множество обладающих всех точек $z,$ этим свойством (то есть множество точек, из которых видно все $)$ называется ядром P. $P$ ,

Если многоугольник в форме звезды является выпуклым , расстояние между любыми двумя его точками (минимальное количество последовательных отрезков, достаточное для соединения этих точек) равно 1, поэтому диаметр соединения многоугольника (максимальное расстояние между всеми парами точек) равно 1. Если многоугольник в форме звезды не является выпуклым, расстояние связи между точкой ядра и любой другой точкой многоугольника равно 1, а расстояние связи между любыми двумя точками, которые находятся в многоугольнике, но за пределами многоугольника. ядро — 1 или 2; в этом случае максимальное расстояние канала равно 2.

Примеры [ править ]

Выпуклые многоугольники имеют форму звезды, а выпуклый многоугольник совпадает со своим ядром.

Правильные звездчатые многоугольники имеют звездообразную форму, центр которой всегда находится в ядре.

Антипараллелограммы и самопересекающиеся шестиугольники Лемуана имеют звездообразную форму с ядром, состоящим из одной точки.

Полигоны видимости имеют звездообразную форму, поскольку каждая точка внутри них по определению должна быть видна в центре.

Алгоритмы [ править ]

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

Каждое ребро многоугольника определяет внутреннюю полуплоскость , полуплоскость, граница которой лежит на линии, содержащей ребро, и которая содержит точки многоугольника в окрестности любой внутренней точки ребра. Ядро многоугольника — это пересечение всех его внутренних полуплоскостей. Пересечение произвольного набора N полуплоскостей можно найти за время Θ ( N log N ), используя подход «разделяй и властвуй» . ^[1] Однако в случае ядер многоугольников возможен более быстрый метод: Lee & Preparata (1979). ^[2] представил алгоритм построения ядра за линейное время.

См. также [ править ]

Монотонный многоугольник

Ссылки [ править ]

^ Jump up to: ^а ^б Франко П. Препарата и Майкл Ян Шамос (1985). Вычислительная геометрия – Введение . Спрингер-Верлаг . ISBN 0-387-96131-3 . 1-е издание; 2-е издание, исправленное и дополненное, 1988 г.
^ Ли, DT ; Препарата, Ф.П. (июль 1979 г.), «Оптимальный алгоритм поиска ядра многоугольника» , Журнал ACM , 26 (3): 415–421, doi : 10.1145/322139.322142 , hdl : 2142/74090 , S2CID 6156190 , заархивировано из оригинала 24 сентября 2017 г.

[PS-1] Jump up to: ^а ^б Франко П. Препарата и Майкл Ян Шамос (1985). Вычислительная геометрия – Введение . Спрингер-Верлаг . ISBN 0-387-96131-3 . 1-е издание; 2-е издание, исправленное и дополненное, 1988 г.

[2] Ли, DT ; Препарата, Ф.П. (июль 1979 г.), «Оптимальный алгоритм поиска ядра многоугольника» , Журнал ACM , 26 (3): 415–421, doi : 10.1145/322139.322142 , hdl : 2142/74090 , S2CID 6156190 , заархивировано из оригинала 24 сентября 2017 г.

[1]

[2]