모노톤 폴리곤

Monotone polygon
녹색은 교차로 1개를, 파란색은 교차로 2개를, 빨간색은 교차로 3개 이상을 나타낸다.상위 두 폴리곤은 L과 관련하여 단조로운 반면, 하위 두 폴리곤은 그렇지 않다.

기하학에서, L에 직교하는 모든 선들이 P의 경계를 최대 두 번 교차하는 경우, 직선 L에 관해서 평면의 다각형 P를 모노톤이라고 한다.[1]

마찬가지로, L과 직교하는 모든 선들이 C와 최대 한 번 교차하는 경우, 폴리곤 체인 C는 직선 L에 관해서 단조라고 불린다.

많은 실용적인 목적을 위해 P의 일부 가장자리가 L과 직교하는 경우를 허용하기 위해 이 정의를 확장할 수 있으며, P에서 두 점을 연결하고 L과 직교하는 선 세그먼트가 완전히 P에 있으면 단순한 다각형을 모노톤이라고 할 수 있다.

단조함수에 대한 용어에 따라, 이전의 정의는 L에 관해서 폴리곤을 엄격하게 단조로 설명한다.

특성.

L이 x축과 일치한다고 가정한다.그러면 모노톤 폴리곤의 가장 왼쪽 정점과 오른쪽 정점이 경계를 두 개의 모노톤 폴리곤 체인으로 분해하여 어떤 체인의 정점이든 자연적인 순서로 가로지르고 있을 때 X 좌표가 단조롭게 증가하거나 감소한다.사실, 이 속성은 단조로운 다각형의 정의에 따라 취해질 수 있으며, 그것은 폴리곤에게 그것의 이름을 부여한다.

볼록 폴리곤은 모든 직선에 대해 단조로운 것이고, 모든 직선에 대해 단조로운 폴리곤은 볼록한 것이다.

선형 시간 알고리즘은 주어진 단순한 다각형이 단조로운 모든 방향을 보고하는 것으로 알려져 있다.[2]단순한 다각형을 두 개의 단조로운 사슬로 분해하는 모든 방법을 보고하는 것이 일반화되었다.[3]

단조로운 폴리곤에 대한 폴리곤 질의의 점은 선형 시간 사전 처리 후(가장 왼쪽 정점과 가장 오른쪽 정점을 찾기 위해) 로그 시간으로 응답할 수 있다.[1]

단조 다각형은 선형 시간으로 삼각측정이 용이할 수 있다.[4]

평면에서 주어진 점 집합에 대해 비토닉 투어는 점을 연결하는 단조로운 다각형이다.고정 방향과 관련하여 주어진 점 집합에 대한 최소 둘레 비토닉 투어는 동적 프로그래밍을 사용하여 다항식 시간에 찾을 수 있다.[5]이러한 미니멀한 비토닉 투어가 단순한 폴리곤임을 쉽게 알 수 있는데, 새 투어의 비토닉성을 보존하면서 한 쌍의 교차 모서리를 짧은 비크로 교체할 수 있다.

폴리곤을 모노톤 폴리곤으로 분할

간단한 폴리곤은 O(n log n) 시간에 단조 폴리곤으로 쉽게 자를 수 있다.단, 삼각형은 단조형 다각형이기 때문에 사실상 다각형을 단조형으로 자르는 것이며, O(n)시간 내에 간단한 다각형에 대해 수행될 수도 있다.[citation needed]

단순 다각형을 균일하게 단일한 폴리곤의 최소 수(즉, 같은 선에 대한 모노톤)로 절단하는 것은 다항식 시간에 수행할 수 있다.[6]

운동계획의 맥락에서, 두 개의 비절연 모노톤 폴리곤은 하나의 번역(즉, 두 개가 서로 다른 반평면으로 직선으로 분리되도록 하나의 폴리곤의 번역이 존재함)으로 분리가 가능하며, 이러한 분리는 선형 시간 내에 발견될 수 있다.[7]

일반화

쓸 수 있는 다각형

폴리곤은 어떤 순간에 폴리곤 영역과의 교차점이 볼록한 집합이 되도록 직선을 전체 폴리곤 위로 연속적으로 이동할 수 있는 경우 스위프블(sweepable)이라고 한다.단조 다각형은 스위프 도중 방향을 변경하지 않는 선으로 스위프할 수 있다.폴리곤은 면적의 어느 부분도 두 번 이상 쓸지 않으면 엄격히 쓸 수 있다.두 가지 유형의 스위프성은 2차 시간 내에 인식된다.[8]

3D

폴리곤 단조로움을 보다 높은 차원으로 단도직입적으로 일반화하는 것은 없다.

한 가지 접근방식에서 보존된 단조성 특성은 L 선이다. L과 직교하는 모든 횡단이 단순한 다각형일 경우 3차원 다면체를 L 방향에서 약하게 단조성이라고 부른다.단면이 볼록하면 다면체를 볼록한 의미로 약하게 단면체라고 한다.[7]두 형식 모두 다항식 시간에 인식될 수 있다.[8]

또 다른 접근방식에서 보존된 1차원 특성은 직교 방향이다.이것은 3차원의 다면 지형 개념에 대해 떠오르게 한다: 각 수직선(즉, Z축에 평행) 선이 최대 1점 또는 세그먼트에서 표면을 교차하는 특성을 가진 다면 표면이다.

참고 항목

  • 직교 볼록성 - 두 개의 상호 직교 방향에 대해 동시에 단조인 폴리곤의 경우, 또한 고정된 방향의 수에 대한 일반화.
  • 별 모양 다각형, 단조형 다각형의 극좌표 아날로그

참조

  1. ^ a b Preparata, Franco P.; Shamos, Michael Ian (1985), Computational Geometry – An Introduction, Springer-Verlag, ISBN 0-387-96131-3, 1st edition: ; 2nd printing, corrected and expanded, 1988: ; Russian translation, 1989
  2. ^ Preparata, Franco P.; Supowit, Kenneth J. (1981), "Testing a simple polygon for monotonicity", Information Processing Letters, 12 (4): 161–164, doi:10.1016/0020-0190(81)90091-0.
  3. ^ Rappaport, David; Rosenbloom, Arnold (1994), "Moldable and castable polygons", Computational Geometry, 4 (4): 219–233, doi:10.1016/0925-7721(94)90020-5.
  4. ^ Fournier, A.; Montuno, D. Y. (1984), "Triangulating simple polygons and equivalent problems", ACM Transactions on Graphics, 3 (2): 153–174, doi:10.1145/357337.357341, ISSN 0730-0301, S2CID 33344266
  5. ^ 알고리즘 소개, 2차 에드, T. H. 코멘, C. E. Leiserson, R. Rivest 및 C. Stein, MIT 출판부, 2001.문제 15-1, 페이지 364.
  6. ^ Liu, Robin (1988), "On decomposing polygons into uniformly monotone parts", Information Processing Letters, 27 (2): 85–89, doi:10.1016/0020-0190(88)90097-X.
  7. ^ a b Toussaint, G. T.; El Gindy, H. A. (1984), "Separation of two monotone polygons in linear time", Robotica, 2 (4): 215–220, doi:10.1017/S0263574700008924.
  8. ^ a b Bose, Prosenjit; van Kreveld, Marc (2005), "Generalizing monotonicity: On recognizing special classes of polygons and polyhedra by computing nice sweeps", International Journal of Computational Geometry & Applications, 15 (6): 591–608, doi:10.1142/S0218195905001877, hdl:1874/24150.