의사각
Pseudotriangle
유클리드 평면 기하학에서, 의사-삼각형(pseudo-triangle)은 상호 접선 볼록 집합 사이에 있는 평면의 단순하게 연결된 부분 집합이다.의사삼각화(의사삼각화)는 평면의 영역을 의사삼각화(pseudorriangulation)로 분할한 것이며, 뾰족한 의사삼각화는 각 정점에서 입사 가장자리가 θ 미만의 각도로 걸쳐 있는 의사삼각화(pseudorriangulation)이다.
"의사각도"와 "의사각도"라는 단어는 수학에서 훨씬 [1]더 오랫동안 다양한 의미로 사용되어 왔지만, 여기서 사용되는 용어는 1993년 미셸 포치올라와 거트 베그터에 의해 평면 내의 볼록한 장애물 사이의 가시 관계와 역각도의 계산과 관련하여 도입되었다.Ileana Streinu(2000, 2005)는 목수 자 문제에 대한 해결책의 일부로 뾰족한 의사 혈관 절개를 처음 고려했는데, 이는 연속적인 움직임에 의해 평면의 모든 단순한 다각형 경로가 곧게 펴질 수 있다는 증거이다.의사 혈관화는 움직이는[2] 물체 간의 충돌 감지 및 동적 그래프 그리기 및 형상 [3]모핑에도 사용되었습니다.최소 강성 평면 [4]그래프의 예로서 강성 이론과 아트 갤러리 정리와의 [5]관련으로 가드를 배치하는 방법에서 뾰족한 의사 혈관도가 발생한다.평면 점 세트의 포격 항갑상선은 뾰족한 의사 [6]혈관 절개를 발생시키지만, 모든 뾰족한 의사 혈관 절개가 이러한 방식으로 발생할 수는 없다.
여기서 설명하는 자료의 많은 부분에 대한 자세한 조사는 Rotte, Santos 및 Streinu(2008)를 참조하십시오.
유사트라이앵글
Pocchiola와 Vegter(1996a,b,c)는 원래 의사 각도를 끝점에서 접선하는 세 개의 매끄러운 볼록 곡선으로 둘러싸인 평면의 단순하게 연결된 영역으로 정의했다.그러나 후속 연구는 부드러운 곡선으로 둘러싸인 영역뿐만 아니라 다각형에 더 일반적으로 적용되고 세 개의 정점에서 0이 아닌 각도를 허용하는 광범위한 정의에 정착했다.이 더 넓은 정의에서, 의사각도는 평면에서 단순히 연결된 영역으로, 세 개의 볼록한 정점을 가지고 있다.이 세 개의 정점을 연결하는 세 개의 경계 곡선은 볼록해야 하며, 같은 경계 곡선의 두 점을 연결하는 선분은 모두 의사 원각의 바깥쪽 또는 경계 위에 있어야 합니다.따라서, 의사각도는 이 세 곡선의 볼록한 선체 사이의 영역이며, 보다 일반적으로 상호 접선 볼록한 세 집합은 그 사이에 있는 의사각도를 형성한다.
알고리즘 어플리케이션에서는 폴리곤인 의사트라이언글의 특성을 파악하는 것이 특히 중요합니다.폴리곤에서 정점은 θ 미만의 내부 각도에 걸쳐 있으면 볼록하고, 그렇지 않으면 오목하다(특히 정확히 θ의 각도는 오목한 것으로 간주한다).폴리곤의 총외각은 2㎜이고 볼록각은 각각 θ 미만이며 오목각은 0 또는 음의 양에 기여하기 때문에 폴리곤은 적어도 3개의 볼록각을 가져야 한다.다각형 의사각은 정확히 세 개의 볼록한 정점이 있는 다각형입니다.특히, 모든 삼각형과 비볼록 사각형은 의사각이다.
의사각도의 볼록한 선체는 삼각형이다.각 볼록 꼭지점 쌍 사이의 의사 각도 경계를 따른 곡선은 삼각형 안에 있거나 모서리 중 하나와 일치합니다.
유사 혈관 형성
의사 혈관화는 평면의 영역을 의사 혈관 안으로 분할하는 것입니다.평면 영역의 삼각 측량은 의사 혈관 조정입니다.동일한 영역의 모든 두 삼각 측량에는 동일한 수의 모서리와 삼각형이 있어야 하지만, 의사 각도에는 해당되지 않습니다. 예를 들어 영역 자체가 n-vertex 다각형 의사 각도인 경우, 해당 영역의 의사 각도에는 1개의 의사 각도 및 n개의 의사 각도 또는 n개의 의사 각도 및 2개의 의사 각도만큼 많은 n개의 의사 각도 및 2개의 의사 각도 값이 있을 수 있습니다.엣지 3개
최소의 의사배향은 T의 서브그래프가 평면의 동일한 볼록영역을 덮는 의사배향 T가 아닌 의사배향이다.n개의 정점이 있는 최소 의사 혈관조절에는 최소 2n - 3개의 가장자리가 있어야 합니다. 정확히 2n - 3개의 가장자리가 있는 경우 뾰족한 의사 혈관조절이어야 하지만 3n - O(1) [7]가장자리가 있는 최소 의사 혈관조절이 존재합니다.
Agarwal 등(2002) 이동점 또는 이동 폴리곤의 의사 혈관화를 유지하기 위한 데이터 구조를 기술한다.이들은 삼각 측량 대신 의사 혈관 조정을 사용하면 입력이 이동함에 따라 알고리즘이 상대적으로 적은 조합 변경으로 이러한 구조를 유지할 수 있으며, 이러한 동적 의사 혈관 조정을 사용하여 움직이는 물체 간의 충돌 검출을 수행한다는 것을 보여준다.
구드문트손 외(2004) 최소 총 엣지 길이를 가진 점 세트 또는 폴리곤의 의사 혈관화를 찾는 문제를 고려하고 이 문제에 대한 근사 알고리즘을 제공한다.
뾰족한 의사 혈관 형성
각 정점에서 입사선 세그먼트가 최대 θ의 각도에 걸쳐 이 특성을 유지하면서 기존의 2개의 정점 사이에 선 세그먼트를 추가할 수 없는 선분의 유한한 비교차 집합으로 정의할 수 있다.뾰족한 의사배향은 볼록한 선체의 의사배향이라는 것을 어렵지 않게 알 수 있다. 모든 볼록한 선체 가장자리는 각도 스팬 특성을 유지하면서 추가할 수 있으며 모든 내부 면은 의사배향이어야 하며 그렇지 않으면 면의 두 꼭지점 사이에 역방향 선분을 추가할 수 있다.
정점이 v개인 뾰족한 의사 혈관 형성에는 정확히 2v - 3개의 [8]가장자리가 있어야 합니다.따라서 오일러 특성을 포함하는 단순한 이중 계수 인수가 뒤따른다. 외측 면은 3개의 볼록 각도를 가진 의사 각도로, 의사 각도는 인접한 가장자리 사이에 3f - 3개의 볼록 각도를 가져야 한다.각 모서리는 두 각도의 시계방향 모서리이므로 v를 제외한 모든 각도가 볼록한 총 2e 각도가 있습니다.따라서, 3f - 3 = 2e - v. 이것을 오일러 방정식 f - e + v = 2와 결합하고 그 결과 도출된 연립 선형 방정식을 풀면 e = 2v - 3이 된다.또한 동일한 인수는 f = v - 1(면 중 하나로 볼록한 선체 포함)을 나타내므로 의사 혈관조절에는 정확히 v - 2개의 의사 혈관조절이 있어야 한다.
마찬가지로 뾰족한 의사 혈관화의 k-vertex 하위 그래프는 정점의 뾰족한 의사 혈관화를 형성하기 위해 완성될 수 있으므로, 하위 그래프는 최대 2k - 3개의 가장자리를 가져야 한다.따라서 뾰족한 의사 혈관도는 정확히 2v - 3개의 에지를 가지며 k-vertex 하위 그래프는 최대 2k - 3개의 에지를 가진다.라만 그래프, 따라서 뾰족한 의사 혈관도는 2차원의 최소 강성 그래프이다.평면 라만 그래프의 평면 도면이 모두 의사 [9]도형이 아닌 경우에도 모든 평면 라만 그래프는 뾰족한 의사 도선으로 그릴 수 있습니다.
뾰족한 의사 각도 조정을 찾는 또 다른 방법은 점 세트를 셸링하는 것입니다. 즉, 모든 점이 제거될 때까지 볼록한 선체 정점을 하나씩 제거하는 것입니다.이 방법으로 형성할 수 있는 제거 시퀀스의 패밀리는 점 세트의 포격 안티로이드이며, 이 제거 프로세스에 의해 형성된 점 세트의 연속된 볼록 선체 가장자리 세트는 의사 혈관화를 [6]형성한다.그러나 모든 뾰족한 의사 혈관 배열을 이 방법으로 형성할 수 있는 것은 아닙니다.
아이홀저 외(2004)는 세트의 볼록한 선체에 속하는 n개 점의 집합은 적어도h−2 Cn−h×3개의 다른 뾰족한 의사 혈관(C는i ith 카탈로니아 수)을 가져야 한다는 것을 보여준다.그 결과 뾰족한 의사 각도가 가장 적은 점 집합이 볼록 다각형의 정점 집합임을 알 수 있습니다.아이홀저 외(2006) 많은 수의 뾰족한 의사 혈관 절개로 점 집합을 조사한다.계산기하학 연구자들은 또한 의사 [10]혈관조절당 작은 시간 내에 설정된 점의 모든 뾰족한 의사 혈관조절을 나열하기 위한 알고리즘을 제공했다.
「 」를 참조해 주세요.
메모들
- ^ "의사 삼각"에 대해서는 예를 들어,196페이지에서 이 논문은 함수 근사에서의 "의사 삼각 조건"을 언급하고 있습니다Whitehead, J. H. C. (1961), "Manifolds with transverse fields in Euclidean space", Annals of Mathematics, 73 (1): 154–212, doi:10.2307/1970286, JSTOR 1970286, MR 0124917.「의사 삼각 관계」에 대해서는, 예를 들면 을 참조해 주세요.
- ^ Agarwal 등(2002).
- ^ Streinu (2006)
- ^ 하스 등(2005)
- ^ Specmann과 Toth(2005).
- ^ a b Har-Peled (2002년).
- ^ Rotte, Wang, Wang 및 Xu(2003)정리 4와 그림 4.
- ^ Streinu(2000년)에 의해 처음 제시되었지만, 여기서 제시하는 주장은 Haas 등으로부터 나온 것이다.(2005), Lema 5.
- ^ 하스 등(2005).
- ^ 베레그(2005);브뢰니만 외(2006).
레퍼런스
- 를 클릭합니다Agarwal, Pankaj K.; Basch, Julien; Guibas, Leonidas J.; Hershberger, John; Zhang, Li (2002), "Deformable free-space tilings for kinetic collision detection", International Journal of Robotics Research, 21 (3): 179–197, doi:10.1177/027836402320556395, S2CID 11907465.
- 캐나다에서의 예비 버전입니다Aichholzer, Oswin; Aurenhammer, Franz; Krasser, Hannes; Speckmann, Bettina (2004), "Convexity minimizes pseudo-triangulations", Computational Geometry Theory and Applications, 28 (1): 3–10, doi:10.1016/j.comgeo.2004.01.002, MR 2070708. Conf. 컴퓨터. 검, 2002년.
- Aichholzer, Oswin; Orden, David; Santos, Francisco; Speckmann, Bettina (2008), "On the number of pseudo-triangulations of certain point sets", Journal of Combinatorial Theory, Series A, 115 (2): 254–278, arXiv:math/0601747, doi:10.1016/j.jcta.2007.06.002, MR 2382515, S2CID 1189243
- 를 클릭합니다Bereg, Sergey (2005), "Enumerating pseudo-triangulations in the plane", Computational Geometry Theory and Applications, 30 (3): 207–222, doi:10.1016/j.comgeo.2004.09.002, MR 2123970.
- 를 클릭합니다Brönnimann, Hervé; Kettner, Lutz; Pocchiola, Michel; Snoeyink, Jack (2006), "Counting and enumerating pointed pseudotriangulations with the greedy flip algorithm", SIAM Journal on Computing, 36 (3): 721–739, doi:10.1137/050631008, MR 2263009.
- Gudmundsson, 요아힘, Levcopoulos,인 크리스토;카말, Lodaya, Meena, Mahajan(2004년),"최소 무게 pseudo-triangulations"(PDF), Lodaya, 카말에;Mahajan, Meena(eds.), FSTTCS 2004년:소프트웨어 기술 이론 컴퓨터 과학의 기초, 강의 노트 컴퓨터 과학으로,. 299–310, arXiv:0705.3888, 3328, Springer-Verlag, pp vol.. doi:10.1007/b104325, 아이 에스비엔 978-3-540-24058-7.
- 하스, 루스, Orden, 데이비드, 로트, 귄터, 산토스, 프란시스코, Servatius인 브리짓, Servatius, 허먼, Souvaine, 다이앤, Streinu, 결의안;Whiteley, 월터(2005년),"평면을 최소화 엄격한 그래프와 pseudo-triangulations", 해석 기하학 이론과 응용, 31일(1–2):31–61, arXiv:math/0307347, doi:10.1016/j.comgeo.2004.07.003, MR2131802, S2.중수부 38637747.
- 를 클릭합니다Har-Peled, Sariel (2002), A comment on pseudo-triangulation in three dimensions, archived from the original on 2006-09-12, retrieved 2007-04-12.
- 9번째 ACM Symp의 예비 버전Pocchiola, Michel; Vegter, Gert (1996a), "The visibility complex", International Journal of Computational Geometry and Applications, 6 (3): 297–308, doi:10.1142/S0218195996000204, archived from the original on 2006-12-03. 계산 기하학(1993) 328–337.
- 를 클릭합니다Pocchiola, Michel; Vegter, Gert (1996b), "Topologically sweeping visibility complexes via pseudotriangulations", Discrete and Computational Geometry, 16 (4): 419–453, doi:10.1007/BF02712876, MR 1414964.
- 를 클릭합니다Pocchiola, Michel; Vegter, Gert (1996c), "Pseudo-triangulations: theory and applications", Proceedings of the 12th Annual ACM Symposium on Computational Geometry, pp. 291–300, doi:10.1145/237218.237398, S2CID 15948239.
- 를 클릭합니다Rote, Günter; Santos, Francisco; Streinu, Ileana (2003), "Expansive motions and the polytope of pointed pseudo-triangulations", Discrete and Computational Geometry — The Goodman–Pollack Festschrift, Springer-Verlag, pp. 699–736, arXiv:math.CO/0206027, doi:10.1007/978-3-642-55566-4_33, S2CID 14689476.
- 를 클릭합니다Rote, Günter; Santos, Francisco; Streinu, Ileana (2008), "Pseudo-triangulations — a survey", Surveys on discrete and computational geometry, Contemporary Mathematics, vol. 453, Providence, RI: American Mathematical Society, pp. 343–410, MR 2405689.
- 를 클릭합니다Rote, Günter; Wang, Cao An; Wang, Lusheng; Xu, Yinfeng (2003), "On constrained minimum pseudotriangulations" (PDF), Computing and Combinatorics, Lecture Notes in Computer Science, vol. 2697, Springer-Verlag, pp. 445–454.
- 를 클릭합니다Speckmann, Bettina; Tóth, Csaba D. (2005), "Allocating vertex π-Guards in simple polygons via pseudo-triangulations", Discrete and Computational Geometry, 33 (2): 345–364, doi:10.1007/s00454-004-1091-9, MR 2121300.
- 를 클릭합니다Streinu, Ileana (2000), "A combinatorial approach to planar non-colliding robot arm motion planning", Proceedings of the 41st Annual Symposium on Foundations of Computer Science, IEEE Computer Society, pp. 443–453, doi:10.1109/SFCS.2000.892132, S2CID 9420124.
- 를 클릭합니다Streinu, Ileana (2005), "Pseudo-triangulations, rigidity and motion planning", Discrete and Computational Geometry, 34 (4): 587–635, doi:10.1007/s00454-005-1184-0, MR 2173930.
- 를 클릭합니다Streinu, Ileana (2006), "Parallel-redrawing mechanisms, pseudo-triangulations and kinetic planar graphs", Proc. Int. Symp. Graph Drawing (GD 2005), Springer-Verlag, Lecture Notes in Computer Science 3843, pp. 421–433.
