В геометрии звездообразный многоугольник — это многоугольная область на плоскости, которая является звездным доменом , то есть многоугольником, содержащим точку, из которой видна вся граница многоугольника .
Формально, многоугольник P имеет форму звезды , если существует точка z такая, что для каждой точки p многоугольника P отрезок полностью лежит внутри 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] . Однако для случая ядер многоугольников возможен более быстрый метод: Ли и Препарата (1979) [2] представили алгоритм для построения ядра за линейное время.
