단순다각형

기하학에서 단순 다각형은 교차하지 않고 구멍이 없는 다각형입니다.즉, 이 곡선은 유한하게 많은 선분으로 구성된 조각별 선형 조던 곡선입니다.이 다각형에는 볼록 다각형, 별 모양 다각형, 모노톤 다각형이 특별한 경우로 포함됩니다.

단순 다각형의 외각의 합은 $2$ π ${\$$displaystyle$ $2$$\$$pi}$입니다$.$ $n개$의$$변을 가진 모든 단순 다각형은 대각선의 $n$ -${\displaystyle 3}$ ${\displaystyle$ n - $3}$으로 삼각형을 만들 수 있고, 미술관 정리에 의해 그 내부는 꼭짓점의 일부 ⌊ ${\displaystyle n}$/ ${\displaystyle 3}$ ⌋ ${\displaystyle \lfloor$ n / $3\rfoor }$에서 볼 수 있습니다.

단순 다각형은 점 인 폴리곤 테스트, 면적 계산, 단순 다각형의 볼록 선체, 삼각 측량 및 유클리드 최단 경로를 포함한 계산 기하학 문제에 대한 입력으로 흔히 볼 수 있습니다.

단순 다각형과 관련된 기하학의 다른 구성은 단순 다각형을 포함하는 등각 지도를 찾는 데 사용되는 슈바르츠-크리스토펠 매핑, 점 집합의 다각화, 다각형에 대한 구성 입체 기하학 공식 및 다각형의 가시성 그래프를 포함합니다.

정의들

단순 다각형(simple polygon)은 직선 세그먼트로 구성된 유클리드 평면의 닫힌 곡선으로, 종단 간에 만나 다각형 체인을 형성합니다.이 체인에서 연속되는 선 세그먼트의 공유 끝점을 제외하고 두 선 세그먼트가 서로 교차할 수 없습니다.^[1]수식어 simple은 생략되는 경우가 있으며, polygon이라는 단어는 simple polygon을 의미하는 것으로 가정됩니다.^[2]

다각형을 이루는 선분을 가장자리 또는 측면이라고 합니다.세그먼트의 끝점을 정점(복수: 정점)^[1] 또는 모서리라고 합니다.가장자리와 꼭짓점은 더 형식적이지만 그래프의 가장자리와 꼭짓점을 포함하는 문맥에서는 모호할 수 있습니다. 이러한 모호함을 피하기 위해 구어체 용어인 측면과 모서리가 더 많이 사용될 수 있습니다.^[3]각 꼭지점에서 정확히 두 개의 모서리가 만나고 모서리의 수는 항상 꼭지점의 수와 같습니다.^[1]일부 소스에서는 두 개의 선분이 직선 각도(180°)^[4]를 형성하도록 허용하는 반면 다른 소스에서는 이를 허용하지 않고 대신 닫힌 다각형 체인의 공선 세그먼트를 하나의 긴 변으로 병합하도록 요구합니다.^[5]두 꼭짓점이 다각형의 변 중 하나의 두 꼭짓점인 경우 인접합니다.^[6]

단순 다각형은 조던 곡선이기 때문에 조던 다각형이라고 불리기도 합니다. 조던 곡선 정리는 이러한 다각형이 평면을 두 영역으로 나눈다는 것을 증명하는 데 사용될 수 있습니다.^[7]실제로 카밀 조단의 이 정리에 대한 원래의 증명은 단순 다각형(증명 없이 기술됨)의 특수한 경우를 출발점으로 삼았습니다.^[8]다각형 내부의 영역(내부)은 유한하지만 0이 아닌 면적을 ^[9]가진 요르단-쇤플라이 정리에 의해 위상학적으로 열린 원반과 동등한 경계 집합을^[1] 형성합니다.^[10]다각형 자체는 위상적으로 원과 동일하며,^[11] 바깥쪽 영역(외부)은 무한한 면적을 가진 무한 연결 열린 집합입니다.^[10]단순 다각형의 공식적인 정의는 일반적으로 선분의 체계로 정의되지만, 단순 다각형을 평면의 닫힌 집합으로 정의하는 것이 가능하며, 이는 다각형의 내부와 선분의 결합입니다.^[1]

단순 다각형의 대각선은 두 개의 다각형 꼭짓점이 끝점으로 있고 그렇지 않은 경우에는 다각형의 내부에 완전히 있는 모든 선분입니다.^[12]

특성.

꼭짓점 중 하나에 있는 단순 다각형의 내각은 꼭짓점에 있는 다각형의 내부에 걸쳐 있는 각도입니다.꼭짓점은 내부 $각도$가$$π {\$displaystyle$ \$pi}($직선 각도, 180°)보다 작으면 볼록합니다.내부 각도가 π ${\displaystyle \pi}$보다 크면 오목합니다$.$ 내부 각도가 θ ${\displaystyle \theta}$인 경우 동일한 꼭짓점에 있는 외부 각도가 보조 π${\displaystyle }$-$$θ {\$displaystyle$ \$pi$-\$theta},$한 방향에서 다음 방향으로 회전하는 각도로 정의됩니다.외각은 볼록한 꼭지점에서 양수이거나 오목한 꼭지점에서 음수입니다.모든 단순 다각형에 대해 외부 각도의 합은 $2$ π ${\displaystyle 2\pi}($1회전, 360°)입니다.따라서 변이$n개인$ 단순 다각형에 대한 내각의 합은$$(${\displaystyle n}$ -${\displaystyle 2}$)${\displaystyle }$π ${\displaystyle (n$ - 2$)\pi }$입니다$.$

모든 단순 다각형은 대각선 부분 집합에 의해 내부-이소 삼각형으로 분할될 수 있습니다.다각형에$$n개의 {\$displaystyle$ n$}$의 변이$$ 있을 때 이러한 파티션에는 $n{\displaystyle }$ -${\displaystyle \mathrm{3개}}$의 ${\displaystyle n-3}$개의$$ 대각선이 포함되어 $n{\displaystyle }$- ${\displaystyle \mathrm{2개}}$의 ${\displaystyle n-2}$개의 삼각형을$$ 형성합니다.그 결과 분할을 다각형 삼각 분할이라고 합니다.^[7]삼각형의 단순 다각형의 모양은 다각형의 내각과 대각선을 공유하는 삼각형 쌍에 의해 형성된 4각형의 교차 비율에 의해 고유하게 결정될 수 있습니다.^[14]

두 귀 정리에 따르면 삼각형이 아닌 모든 단순 다각형에는 두 개의 귀가 있고, 두 개의 이웃이 대각선의 끝점입니다.^[7]관련 정리에 따르면 볼록 다각형이 아닌 모든 단순 다각형에는 입이 있고, 두 개의 이웃이 다각형 외부에 있는 선분의 끝점입니다.정확히 두 개의 귀와 한 개의 입을 가진 다각형을 의인화된 다각형이라고 부릅니다.^[15]

미술관 정리에 따르면, $n개$의 ${\displaystyle$ n$}$개의 정점을 가진 단순 다각형에서, 다각형의 모든 점이 선택된 정점 중 하나에서 보이는 성질을 가진 정점의 부분 집합${\displaystyle n/3\rfloor }$을(를) 최대$$⌊ ${\displaystyle n/3개}$까지 찾을 수 있습니다.즉, 다각형의 각$$ $점{\displaystyle }$ ${\displaystyle p}$에 대해 $p{\displaystyle }$ ${\displaystyle$ p$}$을(를) 선택한 꼭지점에 연결하는$$ 선분이 존재하며, 다각형의 내부 점만 통과합니다.이를 증명하는 한 가지 방법은 다각형의 삼각형에 그래프 채색을 사용하는 것입니다. 삼각형의 각 변 또는 대각선이 서로 다른 색의 끝점 두 개를 갖도록 꼭짓점을 세 가지 색으로 색칠하는 것은 항상 가능합니다.다각형의 각 점은 선택한 삼각형에서 해당 점을 포함하는 삼각형의 세 꼭짓점 중 하나와 같이 각 색의 꼭짓점에 표시됩니다.색상 중 하나는 기껏해야$$⌊ ${\displaystyle n}$/ ${\displaystyle 3}$ ⌋ ${\displaystyle \lfloor n$/ $3\rfoor$}개의 정점에서 사용되어 정리를 증명합니다.

특수한 경우

모든 볼록 다각형은 단순 다각형입니다.단순 다각형의 또 다른 중요한 부류는 별 모양의 다각형으로, 모든 점이 보이는 점(내부 또는 경계)을 가진 다각형입니다.^[1]

직선 $L{\displaystyle }$ ${\displaystyle L}$에 대한 모노톤 다각형은 $L{\displaystyle }$ ${\displaystyle L}$에 수직인 모든 선이 연결된 집합에서 다각형의 내부와 교차하는$$ 다각형입니다$.$이와 동일하게 경계가 두 개의 단조 다각형 사슬로 분할될 수 있는 다각형이며,$$L {\$displaystyle$}에 수직으로 투영될$$때$정점$이 L {\$displaystyle$ L$}$을 따라 체인의 순서와 같습니다$$.^[17]

계산문제

계산 기하학에서 몇 가지 중요한 계산 작업은 단순 다각형 형태의 입력을 포함합니다.

• 폴리곤 테스트의 포인트는 단순 폴리곤 P와 쿼리 포인트 q에 대해 q가 P의 내부에 있는지 여부를 결정하는 것입니다.선형 시간으로 해결할 수 있습니다. 또는 선형 시간으로 주어진 다각형을 데이터 구조로 처리하여 다각형 테스트의 후속 지점을 로그 시간으로 수행할 수 있습니다.^[19]
• 간단한 공식들은 다각형 내부의 넓이를 계산하는 것으로 알려져 있습니다.여기에는 임의의 다각형에 대한 신발 끈 공식과 ^[20]정수의 꼭짓점 좌표를 가진 다각형에 대한 픽의 정리가 포함됩니다.^[11][21]
• 단순한 다각형의 볼록한 선체는 다각형으로 연결되지 않은 점들의 볼록한 선체를 찾는 알고리즘보다 빠른 선형 시간으로도 찾을 수 있습니다.^[5]
• 간단한 다각형의 삼각측량을 구성하는 것은 알고리즘이 복잡하지만 선형 시간으로도 수행할 수 있습니다.또한 동일한 알고리즘을 수정하여 닫힌 다각형 체인이 선형 시간에 단순 다각형을 형성하는지(즉, 자기 교차를 피하는지)를 검정할 수 있습니다.^[22]이는 또한 주어진 다각형에 대해 반드시 최적의 점 수를 사용하지는 않지만 최대 ⌊ ${\displaystyle n/3}$ ⌋ ${\displaystyle \lfloor n/3\rfoor}$ 점을 사용하여 미술관 문제를 해결하는 선형 시간 알고리즘으로 이어집니다.한 번에 하나의 대각선을 대체하는 플립에 의해 동일한 다각형의 임의의 두 삼각형을 서로 변환하는 것은 가능하지만, 제한된 수의 플립만을 사용하여 한 개가 그렇게 할 수 있는지 여부를 결정하는 것은 NP-완전합니다.^[24]
• 삼각법을 서브루틴으로 사용하는 알고리즘은 내부의 두 점을 다각형으로 교차하지 않고 연결하는 평면상 가장 짧은 경로인 측지 경로를 선형 시간으로 확인할 수 있습니다.^[25][26]측지선 중심의 경우에도 마찬가지이며, 측지선 경로의 최대 길이를 다른 모든 점으로 최소화하는 다각형의 한 점입니다.^[25]
• 단순 다각형의 내부 점의 가시성 다각형은 주어진 점에서 다각형 내부로 직접 보이는 점을 선형 시간으로 구성할 수 있습니다.^[27]주어진 선분의 적어도 한 점에서 보이는 부분 집합의 경우에도 마찬가지입니다.^[26]

단순 다각형에 대해 연구된 다른 계산 문제에는 다각형에 대한 가장 긴 대각선 또는 가장 긴 선분 내부의 구성,^[12] 볼록 두개골(주어진 단순 다각형 내에서 가장 큰 볼록 다각형)^[28][29] 및 중앙 축과^[30] 직선 골격을 포함하여 그 모양에 근접한 다양한 1차원 골격의 구성이 포함됩니다.^[31]연구자들은 또한 그들의 오프셋 곡선,^[32] 조합 및 교차점,^[10] 그리고 민코프스키 합을 사용하여 단순 다각형으로 다른 다각형을 만드는 것을 연구했지만,^[33] 이러한 작업의 결과로 항상 단순한 다각형이 만들어지는 것은 아닙니다.실제로 교차 및 차분 작업의 경우, 결과가 1차원 특징 또는 심지어 고립된 점을 포함할 수 있는 집합이 아니라 2차원 영역임을 확인하기 위한 주의가 필요합니다.^[10]

관련구성

리만 매핑 정리에 따르면, 평면의 단순히 연결된 열린 부분 집합은 디스크에 등각적으로 매핑될 수 있습니다.Schwarz-Christofel 매핑은 지정된 꼭짓점 각도와 디스크 경계에 있는 다각형 꼭짓점의 사전 이미지를 사용하여 디스크에서 간단한 다각형으로의 맵을 명시적으로 구성하는 방법을 제공합니다.이러한 사전 정점은 일반적으로 수치적으로 계산됩니다.^[34]

평면에 있는 점들의 단 하나의 선에 있지 않은 모든 유한 집합은 간단한 다각형(180° 각도 허용)의 꼭짓점을 형성하도록 연결될 수 있습니다. 예를 들어, 그러한 다각형 중 하나가 판매원 방문 문제에 대한 해결책입니다.^[35]이와 같이 점을 연결하여 다각형을 형성하는 것을 다각형화라고 합니다.^[36]

모든 단순 다각형은 반평면의 결합과 교차점에서 다각형(내부를 포함한 닫힌 집합)을 구성하는 구성 입체 기하학에서 공식으로 표현될 수 있으며, 다각형의 각 면은 공식에서 반평면으로 한 번 나타납니다.${\displaystyle n}$ 변 $다각형$을 이 표현으로 변환하는 작업은 O $시간{\displaystyle (\mathrm{nlog}}$ ⁡ ${\displaystyle n)}$ ${\displaystyle O(n\log n)}$에 수행할 수 있습니다$.$

단순 다각형의 가시성 그래프는 다각형의 변과 대각선을 나타내는 모서리로 꼭짓점을 연결합니다.^[2]항상 다각형 측면으로 형성된 해밀턴 사이클을 포함합니다.지정된 해밀턴 사이클을 변의 사이클로 지정된 그래프를 가시성 그래프로 하는 다각형을 재구성하는 계산 복잡성은 여전히 열려 있는 문제로 남아 있습니다.^[38]

참고 항목

• 단순다각형의 볼록다각형으로의 연속운동에 관한 카펜터의 법칙문제
• Erd ő스-Nagy 정리, 볼록하지 않은 단순 다각형의 주머니를 반사하여 볼록하게 만드는 과정
• 그물(다면체), 접고 붙여서 주어진 다면체를 만들 수 있는 간단한 다각형
• 구면의 유사한 개념인 구면 다각형
• 약하게 단순한 다각형, 가장자리가 제한된 방식으로 접촉할 수 있는 단순한 다각형의 일반화

참고문헌

외부 링크

• Weisstein, Eric W. "Simple polygon". MathWorld.