별모양 다각형

항성형 다각형은 항성 영역인 평면의 다각형 영역, 즉 폴리곤 경계 전체가 보이는 지점을 포함하는 다각형 영역이다.

형식적으로 다각형 P는 P의 각 점 P에 대해 세그먼트 zp가 전적으로 P 안에 있도록 점 z가 존재하는 경우 항성형이다.^[1] 이 속성을 가진 모든 점 z의 집합(즉, P가 모두 보이는 점 집합)을 P의 커널이라고 한다.

항성형 다각형이 볼록한 경우, 두 점 사이의 연결 거리(이 점들을 연결하기에 충분한 연속선 세그먼트의 최소 수)는 1이므로 폴리곤의 연결 지름(모든 점 쌍에 걸친 최대 연결 거리)은 1이다. 별 모양의 다각형이 볼록하지 않은 경우, 알맹이의 한 점과 폴리곤의 다른 점 사이의 연결 거리는 1인 반면, 폴리곤에 있지만 커널 외부에 있는 두 점 사이의 연결 거리는 1 또는 2이다. 이 경우 최대 연결 거리는 2이다.

예

볼록 폴리곤은 별 모양을 하고 있으며 볼록 폴리곤은 자신의 알맹이와 일치한다.

일반 항성 다각형은 별 모양이며, 중심은 항상 알맹이에 있다.

항타렐로그램과 자간성 레모인 육각형은 별 모양이며, 알맹이는 한 점으로 구성되어 있다.

가시성 폴리곤은 그 안에 있는 모든 점이 정의에 의해 중앙에 보여야 하기 때문에 별 모양이다.

알고리즘

폴리곤이 별 모양인지 시험하고, 커널에서 하나의 지점을 찾는 것은 문제를 선형 프로그램으로 형성하고 저차원 선형 프로그래밍을 위한 기법을 적용함으로써 선형 시간 내에 해결할 수 있다(http://www.inf.ethz.ch/personal/emo/PublFiles/SubexLinProg_ALG16_96.pdf, 페이지 16 참조).

폴리곤의 각 가장자리는 경계선이 가장자리를 포함하는 선에 있고 가장자리의 어떤 내부 지점 근처에 폴리곤의 점을 포함하는 반평면인 내부 반평면을 정의한다. 폴리곤의 알맹이는 모든 내부 반평면의 교차점이다. 임의의 N 하프플레인의 교차점은 분할 및 정복 접근법을 사용하여 using(N log N) 시간에 찾을 수 있다.^[1] 그러나 폴리곤의 낟알의 경우 보다 빠른 방법이 가능하다. 리&프리파타(1979)는 ^[2]커널을 선형 시간대에 구성하는 알고리즘을 제시했다.

참고 항목

• 모노톤 폴리곤

참조