폴리곤화

6개 점 집합의 16개 다각형화

계산기하학에서, 유클리드 평면의 유한한 점 집합의 다각형화는 주어진 점을 ^[1]꼭짓점으로 하는 단순한 다각형이다.폴리곤화는 폴리곤화,^[2] 단순 폴리곤화,^[3] 해밀턴 ^[4]폴리곤화, 비교차 해밀턴 ^[5]사이클 또는 무교차 직선 에지 스패닝 ^[6]사이클이라고도 할 수 있습니다.

한 선에 배치되지 않은 모든 점 집합에는 다항식 시간으로 확인할 수 있는 다각형화가 하나 이상 있습니다.볼록 위치에 있는 점의 경우 하나만 존재하지만 다른 점 집합의 경우 기하급수적으로 많을 수 있습니다.몇 가지 자연 최적화 기준에서 최적의 다각형화를 찾는 것은 어려운 문제이며, 특별한 경우로 출장 세일즈맨 문제를 포함합니다.모든 폴리곤화를 카운트하는 복잡성은 아직 알려지지 않았습니다.

정의.

다각형화는 유클리드 평면에서 정점의 집합으로 주어진 점 집합을 갖는 단순한 다각형이다.폴리곤은 폴리곤의 가장자리인 선 세그먼트에 의해 연속된 쌍으로 연결되는 꼭지점에서 순환 순서로 설명할 수 있습니다.이러한 선 세그먼트의 교차점만 공유 ^[2]끝점에 있는 경우 이러한 방식으로 정의된 폴리곤은 "단순"합니다.

일부 저자는 일반 위치에 있는 점에 대해서만 폴리곤화를 고려합니다. 즉,^[7] 선 위에 세 개가 없습니다.이 가정에서는 폴리곤의 연속된 두 세그먼트 사이의 각도가 180°가 될 수 없습니다.그러나 공선성을 갖는 점 세트를 고려할 때 일반적으로 일부 점에서 다각형화가 180° 각도를 갖는 것이 허용된다.이 경우 이러한 점은 ^[8]모서리 내부가 아니라 정점으로 간주됩니다.

존재.

3 × 3 그리드의 폴리곤화.각 폴리곤에 표시되는 180° 각도가 필요합니다. 이 크기의 그리드의 경우 모든 폴리곤화의 각도는 ^[9]180°입니다.

스타인하우스(1964)는 일렬에 3개가 없는 모든 유한점 집합이 단순한 ^[10]다각형 정점을 형성한다는 것을 관찰했다.단, 한 줄에 세 개도 필요 없는 것은 불필요하게 강합니다.대신 다각형화(180° 각도 허용)의 존재에 필요한 것은 점이 모두 한 선에 있는 것이 아니라는 것입니다.그렇지 않으면 다항식 시간으로 구성할 수 있는 다각형화가 있습니다.폴리곤화를 구성하는 한 가지 방법은 P{\ $displaystyle$ P $}$ 의 볼록 선체에 있는 $q$ 의 점 $q$ { $displaystyle$ q}를 $q$ 선택하는 것이다(지정된 점 중 하나일 필요는 없음).그런 다음q $주변$ 의 점들을 반경 방향으로 정렬하면(q에서 거리로 묶음) ^[7]q $\displaystyle$ q가 $q$ 커널에 있는 $모든$ 점을 통해 별 모양의 폴리곤이 주기적으로 정렬됩니다.Graham 스캔 볼록 선체 알고리즘의 일부 버전에서는 중심점을 방사상으로 정렬하는 동일한 아이디어가 사용되며 $O(n\log n)$ O ( $O(n\log n)$ log $O(n\log n)$ n $O(n\log n)$ ) \ $display style$ O ( $n$ \ $log$ n )시간 $O(n\log n)$ 내에 ^[11] $O(n\log n)$ 할 수 있습니다.180° 각도를 피하는 다각형화가 항상 존재하는 것은 아닙니다.예를 들어 3 × 3 및 5 × 5 사각 그리드의 경우 모든 폴리곤화는 180°^[9] 각도를 사용합니다.

별 모양의 폴리곤화뿐만 아니라 모든 비공선 점 집합에는 단조 폴리곤인 폴리곤화도 있습니다.즉, 일부 직선( $x\displaystyle$ x $)$ -축으로 $x$ 간주할 수 있음)과 관련하여 기준선에 대한 모든 수직선이 단일 간격으로 폴리곤과 교차하거나 전혀 교차하지 않음을 의미합니다.Grünbaum(1994)의 건설은 $(x)-$ 좌표로 $x$ 점을 정렬하고 두 개의 극단점을 통해 선을 긋는 것으로 시작한다.점이 모두 한 선에 있는 것은 아니기 때문에 이 선에 의해 경계된 두 개의 열린 하프플레인 중 적어도 하나는 비어 있지 않아야 합니다.Grünbaum은 두 개의 모노톤 폴리곤 체인을 형성하며, 하나는 비어 있지 않은 하프플레인 내의 포인트이고 다른 하나는 나머지 포인트입니다.이들의 결합은 원하는 모노톤 폴리곤입니다.구분 단계 후 나머지 공사는 선형 ^[4]시간 내에 수행해도 된다.

축-평행 ^[12]가장자리만 사용하여 점 집합의 폴리곤화 여부를 확인하는 것은 NP-완전입니다.그러나 폴리곤화는 존재하는 경우 모든 정점에서 우회전해야 한다는 추가 제약 조건이 있는 경우 고유하게 결정됩니다.점을 통과하는 각 축-평행 선은 짝수의 점을 통과해야 하며, 이 다각형화는 이 선에서 점 쌍을 번갈아 연결해야 합니다.폴리곤화는 점들을 등좌표로 그룹화하고 각 그룹을 다른 ^[13]좌표로 정렬함으로써 $O(n\log n)$ O $O(n\log n)$ log $O(n\log n)$ $O(n\log n)$ ) { $displaystyle$ O $(n\log$ n $)}$ 에서 $O(n\log n)$ 찾을 수 있습니다.모든 점 세트에 대해 최대 1개의 회전은 이 형태의 다각형화를 가질 수 있으며, 이 회전은 다항식 ^[14]시간 내에 다시 찾을 수 있습니다.

최적화

수학의 미해결 문제:

가장 긴 다각형화의 계산 복잡도는 얼마입니까?

(수학에서 풀리지 않은 문제가 더 많다)

최적 다각형화(최적성의 다양한 기준에 대한)를 찾는 문제는 종종 계산적으로 실행할 수 없다.예를 들어, 출장 세일즈맨 문제에 대한 해결책은 주어진 포인트에 대해 교차점이 없습니다.따라서 항상 최소 ^[15]둘레를 사용한 다각형화입니다.NP는 찾기 어렵다.마찬가지로, 최소 또는 최대 면적의 단순 다각형화를 찾는 것은 NP-hard로 ^[3]알려져 있으며, 일부 계산 ^[16]^[17]노력의 대상이 되어 왔다.최대 면적은 항상 볼록 선체 면적의 절반 이상이며, 대략적인 비율은 ^[18]2입니다.최대 둘레를 갖는 단순 다각형화의 정확한 복잡성과 이 문제에 대한 일정한 근사 비율의 존재는 알려지지 ^[5]않았다.가장 긴 모서리의 길이를 최소화하는 폴리곤화도 NP-hard이며 3 $(\$ 나은 근사 비율에 근접하기 어렵다. 상수 계수 근사치는 알려져 ^[19]있지 않다.

출장 세일즈맨 문제에 대한 최적의 해결책이 아닌 경우에는 교차점이 있을 수 있지만, 전체 길이를 줄이는 로컬 최적화 단계를 통해 모든 교차점을 제거할 수 있습니다.각 단계에서 교차를 제거하는 단계를 사용하면 다항식 시간에 ^[20]이 작업을 수행할 수 있지만, 이 제한 없이 기하급수적인 ^[21]수의 단계를 사용하는 로컬 최적화 시퀀스가 존재합니다.

가장 짧은 비트론 둘러보기(지정된 포인트를 통과하는 최소 주변 단조 폴리곤)는 항상 다각형화이며 다항식 ^[22]시간으로 찾을 수 있습니다.

계산

수학의 미해결 문제:

다각형화를 셀 때 계산 복잡도는 얼마나 됩니까?

(수학에서 풀리지 않은 문제가 더 많다)

특정 점 세트의 모든 폴리곤화를 카운트하는 문제는 NP의 의사결정 문제와 관련된 카운트 문제의 클래스인 #P에 속합니다.그러나 이것이 #P-complete인지 아니면 계산 복잡성이 어느 정도인지는 ^[23]^[24]알 수 없습니다.점 집합은 ^[1]볼록한 위치에 있는 경우에만 정확히 하나의 다각형화를 가집니다.폴리곤화 수가 $.$ ({ $displaystyle 4.64^{n$ ^[25]인 $n개$ ({ $displaystyle$ n $n$ }) $포인트$ 세트가 있으며, $n개$ ({ $displaystyle$ n $})$ 포인트 $n$ 세트마다 최대 $54.6^{n}$ . $({$ 54 $)$ 이 있습니다. $6^{n}}$ 다각형화 $54.6^{n}$ .^[6]

평면 분리기 정리를 점의 라벨 삼각측량에 적용하는 방법을 사용하여 하위 지수 시간 $n^{O({\sqrt {n}})}$ {\ $displaystyle n}개$ 점 $n^{O({\sqrt {n}})}$ 의 모든 폴리곤화를 셀 수 있습니다 $n^{O({\sqrt {n}})}$ ^[26]동적 프로그래밍은 다항식 시간에 모든 단조 폴리곤화를 카운트하기 위해 사용될 수 있으며, 이 계산의 결과는 랜덤 단조 폴리곤화를 ^[27]생성하기 위해 사용될 수 있다.

시대

수학의 미해결 문제:

로컬 이동이 모든 점 세트에 대해 다각형화 상태 공간을 연결할 수 있습니까?

(수학에서 풀리지 않은 문제가 더 많다)

플립 또는 VE^[28] 플립으로 동일한 점을 통해 다른 폴리곤으로 변경할 수 없는 폴리곤

모든 폴리곤화 시스템이 폴리곤화의 가장자리 경계 수를 변경하는 로컬 이동 하에서 연결된 상태 공간을 형성하는 것이 가능한지 여부는 알려지지 않았다.가능한 경우 상태 공간에 그래프 횡단을 적용하여 모든 폴리곤화를 생성하는 알고리즘의 일부로 사용할 수 있습니다.이 문제의 경우 폴리곤화의 두 모서리를 제거하고 두 개의 다른 모서리로 대체하는 플립이나 세 개의 모서리를 제거하고 두 개의 정점을 공유하는 VE 플립을 고려하는 것으로 충분하지 않습니다.같은 점 세트에 다른 폴리곤화가 ^[28]있더라도 플립 또는 VE 플립이 불가능한 폴리곤화가 존재합니다.

각 점을 정점으로 한 번 이상 사용하는 약하게 단순한 폴리곤인 폴리곤 랩은 모든 폴리곤화를 포함하며 로컬 ^[2]이동을 통해 연결됩니다.폴리곤의 또 다른 일반적인 클래스인 주변 폴리곤은 주어진 점 중 일부를 정점으로 가지고 모든 점을 둘러싸는 단순한 폴리곤입니다.이들은 다시 로컬로 연결되며 폴리곤당 다항 시간으로 나열될 수 있습니다.이 알고리즘은 볼록한 선체를 뿌리로 하고 하나의 정점을 제거함으로써 얻어진 서로 둘러싸인 폴리곤의 부모로 폴리곤의 트리를 구성합니다(폴리곤의 바깥쪽에 두 개의 귀 정리를 적용함으로써 가능한 것으로 증명됨).그런 다음 이 트리에 역방향 검색 알고리즘을 적용하여 폴리곤을 나열합니다.이 방법의 결과, 모든 $2^{O(n)}$ 는 지수 시간(2 O $2^{O(n)}$ ( $2^{O(n)}$ ) { $style$ 2 $^{O$ $n$ $(n)})$ $n$ 다항식 ^[29]공간에 나열할 수 있습니다.

적용들

고전적인 점 연결 퍼즐은 점들을 순차적으로 연결하여 예기치 않은 모양을 형성하며,^[30] 종종 교차하지 않습니다.출장 세일즈맨 문제와 그 변형에는 많은 ^[31]응용이 있습니다.폴리곤화는 또한 산란된 데이터 포인트에서 윤곽선을 재구성하고 영상 ^[32]분석에서 경계 추적에도 적용됩니다.

「」를 참조해 주세요.

덴조이-리에즈 정리, 요르단 호로 연결할 수 있는 무한히 많은 점 집합

레퍼런스

^ ^a ^b Arkin, Esther M.; Fekete, Sándor P.; Hurtado, Ferran; Mitchell, Joseph S. B.; Noy, Marc; Sacristán, Vera; Sethia, Saurabh (2003), "On the reflexivity of point sets", in Aronov, Boris; Basu, Saugata; Pach, János; Sharir, Micha (eds.), Discrete and Computational Geometry: The Goodman-Pollack Festschrift, Algorithms and Combinatorics, vol. 25, Berlin: Springer, pp. 139–156, doi:10.1007/978-3-642-55566-4_6, MR 2038472
^ ^a ^b ^c Damian, Mirela; Flatland, Robin; O'Rourke, Joseph; Ramaswami, Suneeta (2010), "Connecting polygonizations via stretches and twangs", Theory of Computing Systems, 47 (3): 674–695, doi:10.1007/s00224-009-9192-8, MR 2652036
^ ^a ^b Fekete, S. P. (2000), "On simple polygonalizations with optimal area", Discrete & Computational Geometry, 23 (1): 73–110, doi:10.1007/PL00009492, MR 1727124
^ ^a ^b Grünbaum, Branko (1994), "Hamiltonian polygons and polyhedra" (PDF), Geombinatorics, 3 (3): 83–89, MR 1326479
^ ^a ^b Dumitrescu, Adrian; Tóth, Csaba D. (2010), "Long non-crossing configurations in the plane", Discrete & Computational Geometry, 44 (4): 727–752, doi:10.1007/s00454-010-9277-9, MR 2728029
^ ^a ^b Sharir, Micha; Sheffer, Adam; Welzl, Emo (2013), "Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique", Journal of Combinatorial Theory, Series A, 120 (4): 777–794, doi:10.1016/j.jcta.2013.01.002, MR 3022612
^ ^a ^b Deneen, Linda; Shute, Gary (1988), "Polygonizations of point sets in the plane", Discrete & Computational Geometry, 3 (1): 77–87, doi:10.1007/BF02187898, MR 0918181
^ Malkevitch, Joseph (2016), "Are Precise Definitions a Good Idea?", AMS Feature Column, American Mathematical Society
^ ^a ^b Chow, Sam; Gafni, Ayla; Gafni, Paul (March 2021), "Connecting the dots: maximal polygons on a square grid", Mathematics Magazine, 94 (2): 118–124, doi:10.1080/0025570x.2021.1869493, MR 4241975
^ Steinhaus, Hugo (1964), One Hundred Problems in Elementary Mathematics, Basic Books, pp. 17, 85–86
^ Graham, R. L. (June 1972), "An efficient algorithm for determining the convex hull of a finite planar set" (PDF), Information Processing Letters, 1 (4): 132–133, doi:10.1016/0020-0190(72)90045-2
^ Rappaport, David (1986), On the complexity of computing orthogonal polygons from a set of points, Technical Report, vol. SOCS-86.9, Montreal: McGill University
^ O'Rourke, Joseph (1988), "Uniqueness of orthogonal connect-the-dots", in Toussaint, Godfried T. (ed.), Computational Morphology: A Computational Geometric Approach to the Analysis of Form, Machine Intelligence and Pattern Recognition, vol. 6, Amsterdam: North-Holland, pp. 97–104, doi:10.1016/B978-0-444-70467-2.50013-8, MR 0994001
^ Löffler, Maarten; Mumford, Elena (2011), "Connected rectilinear graphs on point sets", Journal of Computational Geometry, 2 (1): 1–15, doi:10.20382/v2i1a1, MR 2786032
^ Quintas, L. V.; Supnick, Fred (1965), "On some properties of shortest Hamiltonian circuits", The American Mathematical Monthly, 72: 977–980, doi:10.2307/2313333, JSTOR 2313333, MR 0188872
^ Demaine, Erik D.; Fekete, Sándor P.; Keldenich, Phillip; Krupke, Dominik; Mitchell, Joseph S. B. (2022), "Area-optimal simple polygonalizations: the CG challenge 2019", ACM Journal of Experimental Algorithmics, 27: Art. 2.4, 12, doi:10.1145/3504000, MR 4390039
^ Ramos, Natanael; de Rezende, Pedro J.; de Souza, Cid C. (2022), "Optimal area polygonization problems: exact solutions through geometric duality", Computers & Operations Research, 145, Paper No. 105842, doi:10.1016/j.cor.2022.105842, MR 4418151
^ Fekete, Sándor P. (1992), Geometry and the Travelling Salesman Problem (Doctoral dissertation), University of Waterloo, ProQuest 304035266 볼록 선체의 절반이 넘는 면적의 다각형화는 정리 4.2.1(56페이지)을 참조하십시오.
^ Fekete, Sándor P.; Keldenich, Phillip (2018), "Computing crossing-free configurations with minimum bottleneck" (PDF), 34th European Workshop on Computational Geometry, Free University of Berlin, pp. 23:1–23:6
^ van Leeuwen, Jan; Schoone, Anneke A. (1981), "Untangling a travelling salesman tour in the plane" (PDF), in Mühlbacher, Jörg R. (ed.), Proceedings of the 7th Conference Graphtheoretic Concepts in Computer Science (WG '81), Linz, Austria, June 15-17, 1981, Hanser, Munich, pp. 87–98, MR 0708744
^ Englert, Matthias; Röglin, Heiko; Vöcking, Berthold (2014), "Worst case and probabilistic analysis of the 2-opt algorithm for the TSP", Algorithmica, 68 (1): 190–264, doi:10.1007/s00453-013-9801-4, MR 3147481
^ de Berg, Mark; Buchin, Kevin; Jansen, Bart M. P.; Woeginger, Gerhard (2016), "Fine-Grained Complexity Analysis of Two Classic TSP Variants", in Chatzigiannakis, Ioannis; Mitzenmacher, Michael; Rabani, Yuval; Sangiorgi, Davide (eds.), 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Leibniz International Proceedings in Informatics (LIPIcs), vol. 55, Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, pp. 5:1–5:14, doi:10.4230/LIPIcs.ICALP.2016.5, ISBN 978-3-95977-013-2
^ Mitchell, Joseph S. B.; O'Rourke, Joseph (2001), "Computational geometry column 42", International Journal of Computational Geometry and Applications, 11 (5): 573–582, arXiv:cs/0108021, doi:10.1142/S0218195901000651, MR 1862888
^ O'Rourke, Joseph (January 1, 2003), "Problem 16: Simple Polygonalizations", The Open Problems Project
^ García, Alfredo; Noy, Marc; Tejel, Javier (2000), "Lower bounds on the number of crossing-free subgraphs of $K_{N}$ ", Computational Geometry: Theory & Applications, 16 (4): 211–221, doi:10.1016/S0925-7721(00)00010-9, MR 1775294
^ Marx, Dániel; Miltzow, Tillmann (2016), "Peeling and nibbling the cactus: subexponential-time algorithms for counting triangulations and related problems", in Fekete, Sándor P.; Lubiw, Anna (eds.), 32nd International Symposium on Computational Geometry, SoCG 2016, June 14-18, 2016, Boston, MA, USA, LIPIcs, vol. 51, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 52:1–52:16, arXiv:1603.07340, doi:10.4230/LIPIcs.SoCG.2016.52, MR 3540894
^ Zhu, Chong; Sundaram, Gopalakrishnan; Snoeyink, Jack; Mitchell, Joseph S. B. (1996), "Generating random polygons with given vertices", Computational Geometry: Theory & Applications, 6 (5): 277–290, doi:10.1016/0925-7721(95)00031-3, MR 1408922
^ ^a ^b Hernando, Carmen; Houle, Michael E.; Hurtado, Ferran (2002), "On local transformation of polygons with visibility properties", Theoretical Computer Science, 289 (2): 919–937, doi:10.1016/S0304-3975(01)00409-1, MR 1945256
^ Yamanaka, Katsuhisa; Avis, David; Horiyama, Takashi; Okamoto, Yoshio; Uehara, Ryuhei; Yamauchi, Tanami (2021), "Algorithmic enumeration of surrounding polygons" (PDF), Discrete Applied Mathematics, 303: 305–313, doi:10.1016/j.dam.2020.03.034, MR 4310502
^ Löffler, Maarten; Kaiser, Mira; van Kapel, Tim; Klappe, Gerwin; van Kreveld, Marc J.; Staals, Frank (2014), "The Connect-The-Dots family of puzzles: design and automatic generation", ACM Transactions on Graphics, 33 (4): 72:1–72:10, doi:10.1145/2601097.2601224
^ Cook, William J. (2012), "Chapter 3: The salesman in action", In pursuit of the traveling salesman, Princeton University Press, Princeton, NJ, pp. 44–61, ISBN 978-0-691-15270-7, MR 2866515
^ Stelldinger, Peer (2010), "Connect the dots: the reconstruction of region boundaries from contour sampling points", in Köthe, Ullrich; Montanvert, Annick; Soille, Pierre (eds.), Applications of Discrete Geometry and Mathematical Morphology - First International Workshop, WADGMM 2010, Istanbul, Turkey, August 22, 2010, Revised Selected Papers, Lecture Notes in Computer Science, vol. 7346, Springer, pp. 1–13, doi:10.1007/978-3-642-32313-3_1

[reflexivity-1] Arkin, Esther M.; Fekete, Sándor P.; Hurtado, Ferran; Mitchell, Joseph S. B.; Noy, Marc; Sacristán, Vera; Sethia, Saurabh (2003), "On the reflexivity of point sets", in Aronov, Boris; Basu, Saugata; Pach, János; Sharir, Micha (eds.), Discrete and Computational Geometry: The Goodman-Pollack Festschrift, Algorithms and Combinatorics, vol. 25, Berlin: Springer, pp. 139–156, doi:10.1007/978-3-642-55566-4_6, MR 2038472

[dfor-2] Damian, Mirela; Flatland, Robin; O'Rourke, Joseph; Ramaswami, Suneeta (2010), "Connecting polygonizations via stretches and twangs", Theory of Computing Systems, 47 (3): 674–695, doi:10.1007/s00224-009-9192-8, MR 2652036

[fekete-3] Fekete, S. P. (2000), "On simple polygonalizations with optimal area", Discrete & Computational Geometry, 23 (1): 73–110, doi:10.1007/PL00009492, MR 1727124

[grunbaum-4] Grünbaum, Branko (1994), "Hamiltonian polygons and polyhedra" (PDF), Geombinatorics, 3 (3): 83–89, MR 1326479

[long-5] Dumitrescu, Adrian; Tóth, Csaba D. (2010), "Long non-crossing configurations in the plane", Discrete & Computational Geometry, 44 (4): 727–752, doi:10.1007/s00454-010-9277-9, MR 2728029

[ssw-6] Sharir, Micha; Sheffer, Adam; Welzl, Emo (2013), "Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique", Journal of Combinatorial Theory, Series A, 120 (4): 777–794, doi:10.1016/j.jcta.2013.01.002, MR 3022612

[star-shaped-7] Deneen, Linda; Shute, Gary (1988), "Polygonizations of point sets in the plane", Discrete & Computational Geometry, 3 (1): 77–87, doi:10.1007/BF02187898, MR 0918181

[precise-8] Malkevitch, Joseph (2016), "Are Precise Definitions a Good Idea?", AMS Feature Column, American Mathematical Society

[grid-9] Chow, Sam; Gafni, Ayla; Gafni, Paul (March 2021), "Connecting the dots: maximal polygons on a square grid", Mathematics Magazine, 94 (2): 118–124, doi:10.1080/0025570x.2021.1869493, MR 4241975

[steinhaus-10] Steinhaus, Hugo (1964), One Hundred Problems in Elementary Mathematics, Basic Books, pp. 17, 85–86

[graham-11] Graham, R. L. (June 1972), "An efficient algorithm for determining the convex hull of a finite planar set" (PDF), Information Processing Letters, 1 (4): 132–133, doi:10.1016/0020-0190(72)90045-2

[rappaport-12] Rappaport, David (1986), On the complexity of computing orthogonal polygons from a set of points, Technical Report, vol. SOCS-86.9, Montreal: McGill University

[orthogonal-13] O'Rourke, Joseph (1988), "Uniqueness of orthogonal connect-the-dots", in Toussaint, Godfried T. (ed.), Computational Morphology: A Computational Geometric Approach to the Analysis of Form, Machine Intelligence and Pattern Recognition, vol. 6, Amsterdam: North-Holland, pp. 97–104, doi:10.1016/B978-0-444-70467-2.50013-8, MR 0994001

[rotate-14] Löffler, Maarten; Mumford, Elena (2011), "Connected rectilinear graphs on point sets", Journal of Computational Geometry, 2 (1): 1–15, doi:10.20382/v2i1a1, MR 2786032

[qs-15] Quintas, L. V.; Supnick, Fred (1965), "On some properties of shortest Hamiltonian circuits", The American Mathematical Monthly, 72: 977–980, doi:10.2307/2313333, JSTOR 2313333, MR 0188872

[contest-16] Demaine, Erik D.; Fekete, Sándor P.; Keldenich, Phillip; Krupke, Dominik; Mitchell, Joseph S. B. (2022), "Area-optimal simple polygonalizations: the CG challenge 2019", ACM Journal of Experimental Algorithmics, 27: Art. 2.4, 12, doi:10.1145/3504000, MR 4390039

[area-ilp-17] Ramos, Natanael; de Rezende, Pedro J.; de Souza, Cid C. (2022), "Optimal area polygonization problems: exact solutions through geometric duality", Computers & Operations Research, 145, Paper No. 105842, doi:10.1016/j.cor.2022.105842, MR 4418151

[tsp-18] Fekete, Sándor P. (1992), Geometry and the Travelling Salesman Problem (Doctoral dissertation), University of Waterloo, ProQuest 304035266 볼록 선체의 절반이 넘는 면적의 다각형화는 정리 4.2.1(56페이지)을 참조하십시오.

[bottleneck-19] Fekete, Sándor P.; Keldenich, Phillip (2018), "Computing crossing-free configurations with minimum bottleneck" (PDF), 34th European Workshop on Computational Geometry, Free University of Berlin, pp. 23:1–23:6

[vls-20] van Leeuwen, Jan; Schoone, Anneke A. (1981), "Untangling a travelling salesman tour in the plane" (PDF), in Mühlbacher, Jörg R. (ed.), Proceedings of the 7th Conference Graphtheoretic Concepts in Computer Science (WG '81), Linz, Austria, June 15-17, 1981, Hanser, Munich, pp. 87–98, MR 0708744

[erv-21] Englert, Matthias; Röglin, Heiko; Vöcking, Berthold (2014), "Worst case and probabilistic analysis of the 2-opt algorithm for the TSP", Algorithmica, 68 (1): 190–264, doi:10.1007/s00453-013-9801-4, MR 3147481

[bbjw-22] Berg, Mark; Buchin, Kevin; Jansen, Bart M. P.; Woeginger, Gerhard (2016), "Fine-Grained Complexity Analysis of Two Classic TSP Variants", in Chatzigiannakis, Ioannis; Mitzenmacher, Michael; Rabani, Yuval; Sangiorgi, Davide (eds.), 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Leibniz International Proceedings in Informatics (LIPIcs), vol. 55, Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, pp. 5:1–5:14, doi:10.4230/LIPIcs.ICALP.2016.5, ISBN 978-3-95977-013-2

[cg42-23] Mitchell, Joseph S. B.; O'Rourke, Joseph (2001), "Computational geometry column 42", International Journal of Computational Geometry and Applications, 11 (5): 573–582, arXiv:cs/0108021, doi:10.1142/S0218195901000651, MR 1862888

[topp-24] O'Rourke, Joseph (January 1, 2003), "Problem 16: Simple Polygonalizations", The Open Problems Project

[gnt-25] García, Alfredo; Noy, Marc; Tejel, Javier (2000), "Lower bounds on the number of crossing-free subgraphs of $K_{N}$ ", Computational Geometry: Theory & Applications, 16 (4): 211–221, doi:10.1016/S0925-7721(00)00010-9, MR 1775294

[cactus-26] Marx, Dániel; Miltzow, Tillmann (2016), "Peeling and nibbling the cactus: subexponential-time algorithms for counting triangulations and related problems", in Fekete, Sándor P.; Lubiw, Anna (eds.), 32nd International Symposium on Computational Geometry, SoCG 2016, June 14-18, 2016, Boston, MA, USA, LIPIcs, vol. 51, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 52:1–52:16, arXiv:1603.07340, doi:10.4230/LIPIcs.SoCG.2016.52, MR 3540894

[zssm-27] Zhu, Chong; Sundaram, Gopalakrishnan; Snoeyink, Jack; Mitchell, Joseph S. B. (1996), "Generating random polygons with given vertices", Computational Geometry: Theory & Applications, 6 (5): 277–290, doi:10.1016/0925-7721(95)00031-3, MR 1408922

[hhh-28] Hernando, Carmen; Houle, Michael E.; Hurtado, Ferran (2002), "On local transformation of polygons with visibility properties", Theoretical Computer Science, 289 (2): 919–937, doi:10.1016/S0304-3975(01)00409-1, MR 1945256

[yahouy-29] Yamanaka, Katsuhisa; Avis, David; Horiyama, Takashi; Okamoto, Yoshio; Uehara, Ryuhei; Yamauchi, Tanami (2021), "Algorithmic enumeration of surrounding polygons" (PDF), Discrete Applied Mathematics, 303: 305–313, doi:10.1016/j.dam.2020.03.034, MR 4310502

[ctd-30] Löffler, Maarten; Kaiser, Mira; van Kapel, Tim; Klappe, Gerwin; van Kreveld, Marc J.; Staals, Frank (2014), "The Connect-The-Dots family of puzzles: design and automatic generation", ACM Transactions on Graphics, 33 (4): 72:1–72:10, doi:10.1145/2601097.2601224

[pursuit-31] Cook, William J. (2012), "Chapter 3: The salesman in action", In pursuit of the traveling salesman, Princeton University Press, Princeton, NJ, pp. 44–61, ISBN 978-0-691-15270-7, MR 2866515

[contour-32] Stelldinger, Peer (2010), "Connect the dots: the reconstruction of region boundaries from contour sampling points", in Köthe, Ullrich; Montanvert, Annick; Soille, Pierre (eds.), Applications of Discrete Geometry and Mathematical Morphology - First International Workshop, WADGMM 2010, Istanbul, Turkey, August 22, 2010, Revised Selected Papers, Lecture Notes in Computer Science, vol. 7346, Springer, pp. 1–13, doi:10.1007/978-3-642-32313-3_1

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

Search

폴리곤화

네임스페이스

더

목차

정의.

존재.

최적화

계산

시대

적용들

「」를 참조해 주세요.

레퍼런스

Search

폴리곤화

정의.

존재.

최적화

계산

시대

적용들

「 」를 참조해 주세요.

레퍼런스

「」를 참조해 주세요.