Non-crossing Hamiltonian paths and cycles in output-polynomial time. (English) Zbl 07921943
Summary: We show that, for planar point sets, the number of non-crossing Hamiltonian paths is polynomially bounded in the number of non-crossing paths, and the number of non-crossing Hamiltonian cycles (polygonalizations) is polynomially bounded in the number of surrounding cycles. As a consequence, we can list the non-crossing Hamiltonian paths or the polygonalizations, in time polynomial in the output size, by filtering the output of simple backtracking algorithms for non-crossing paths or surrounding cycles respectively. We do not assume that the points are in general position. To prove these results we relate the numbers of non-crossing structures to two easily-computed parameters of the point set: the minimum number of points whose removal results in a collinear set, and the number of points interior to the convex hull. These relations also lead to polynomial-time approximation algorithms for the numbers of structures of all four types, accurate to within a constant factor of the logarithm of these numbers.
Keywords:
polygonalization; non-crossing Hamiltonian path; output-sensitive enumeration; approximate countingReferences:
| [1] | Aichholzer, O.; Aurenhammer, F.; Huemer, C.; Vogtenhuber, B., Gray code enumeration of plane straight-line graphs, Graphs Combin., 23, 5, 467-479, 2007 · Zbl 1134.05035 · doi:10.1007/s00373-007-0750-z |
| [2] | Ajtai, M.; Chvátal, V.; Newborn, MM; Szemerédi, E.; Rosa, A.; Sabidussi, G.; Turgeon, J., Crossing-free subgraphs, Theory and Practice of Combinatorics: a collection of articles honoring Anton Kotzig on the occasion of his sixtieth birthday Annals of Discrete Mathematics, 9-12, 1982, Amsterdam: North-Holland, Amsterdam · Zbl 0502.05021 · doi:10.1016/S0304-0208(08)73484-4 |
| [3] | Alon, N.; Rajagopalan, S.; Suri, S., Long non-crossing configurations in the plane, Fund. Inform., 22, 4, 385-394, 1995 · Zbl 0830.68001 · doi:10.3233/FI-1995-2245 |
| [4] | Alvarez, V.; Bringmann, K.; Curticapean, R.; Ray, S., Counting triangulations and other crossing-free structures via onion layers, Discrete Comput. Geom., 53, 4, 675-690, 2015 · Zbl 1325.68247 · doi:10.1007/s00454-015-9672-3 |
| [5] | Avis, D.; Fukuda, K., Reverse search for enumeration, Discrete Appl. Math., 65, 1-3, 21-46, 1996 · Zbl 0854.68070 · doi:10.1016/0166-218X(95)00026-N |
| [6] | Bandyapadhyay, S.; Banik, A.; Bhore, S.; Nöllenburg, M., Geometric planar networks on bichromatic collinear points, Theoret. Comput. Sci., 895, 124-136, 2021 · Zbl 1514.68198 · doi:10.1016/j.tcs.2021.09.035 |
| [7] | Bespamyatnikh, S., An efficient algorithm for enumeration of triangulations, Comput. Geom. Theory Appl., 23, 3, 271-279, 2002 · Zbl 1018.65029 · doi:10.1016/S0925-7721(02)00111-6 |
| [8] | Cheon, G-S, Choi, Hong Joon, Esteban, Guillermo, Song, Minho: Enumeration of bipartite non-crossing geometric graphs, Discrete Appl. Math., 317, 86-100, 2022 · Zbl 1490.05114 · doi:10.1016/j.dam.2022.04.008 |
| [9] | Damian, M.; Flatland, R.; O’Rourke, J.; Ramaswami, S., Connecting polygonizations via stretches and twangs, Theory Comput. Syst., 47, 3, 674-695, 2010 · Zbl 1204.68243 · doi:10.1007/s00224-009-9192-8 |
| [10] | Deineko, VG; Hoffmann, M.; Okamoto, Y.; Woeginger, GJ, The traveling salesman problem with few inner points, Oper. Res. Lett., 34, 1, 106-110, 2006 · Zbl 1080.90064 · doi:10.1016/J.ORL.2005.01.002 |
| [11] | Demaine, ED; Fekete, SP; Keldenich, P.; Krupke, D.; Mitchell, JSB, Area-optimal simple polygonalizations the CG challenge 2019, ACM J. Exp. Algorithmics, 2022 · Zbl 1521.68234 · doi:10.1145/3504000 |
| [12] | Dumitrescu, A.; Tóth, CD, Long non-crossing configurations in the plane, Discrete Comput. Geom., 44, 4, 727-752, 2010 · Zbl 1207.68416 · doi:10.1007/s00454-010-9277-9 |
| [13] | Eppstein, D., Forbidden Configurations in Discrete Geometry, 2018, Cambridge: Cambridge University Press, Cambridge · Zbl 1417.52001 · doi:10.1017/9781108539180 |
| [14] | Eppstein, D., Counting polygon triangulations is hard, Discrete Comput. Geom., 64, 4, 1210-1234, 2020 · Zbl 1460.52022 · doi:10.1007/s00454-020-00251-7 |
| [15] | Fekete, SP, On simple polygonalizations with optimal area, Discrete Comput. Geom., 23, 1, 73-110, 2000 · Zbl 0948.68128 · doi:10.1007/PL00009492 |
| [16] | Flajolet, P.; Noy, M., Analytic combinatorics of non-crossing configurations, Discrete Math., 204, 1-3, 203-229, 1999 · Zbl 0939.05005 · doi:10.1016/S0012-365X(98)00372-0 |
| [17] | García, A.; Noy, M.; Tejel, J., Lower bounds on the number of crossing-free subgraphs of \(K_N\), Comput. Geom. Theory Appl., 16, 4, 211-221, 2000 · Zbl 0966.68158 · doi:10.1016/S0925-7721(00)00010-9 |
| [18] | Gawrychowski, P., Rusak, D.: Euclidean TSP with few inner points in linear space. In Hee-Kap Ahn and Chan-Su Shin, editors, Algorithms and Computation - 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings, volume 8889 of Lecture Notes in Computer Science, pp. 701-713. Springer, (2014). doi:10.1007/978-3-319-13075-0_55 · Zbl 1433.68494 |
| [19] | Guggenheimer, H., The Jordan curve theorem and an unpublished manuscript by Max Dehn, Arch. Hist. Exact Sci., 17, 2, 193-200, 1977 · Zbl 0357.01023 · doi:10.1007/BF02464980 |
| [20] | Hernando, C.; Houle, ME; Hurtado, F., On local transformation of polygons with visibility properties, Theoret. Comput. Sci., 289, 2, 919-937, 2002 · Zbl 1061.68168 · doi:10.1016/S0304-3975(01)00409-1 |
| [21] | Hoffmann, M.; Schulz, A.; Sharir, M.; Sheffer, A.; Tóth, CD; Welzl, E.; Pach, J., Counting plane graphs: flippability and its applications, Thirty Essays on Geometric Graph Theory, 303-325, 2013, New York: Springer, New York · Zbl 1272.05080 · doi:10.1007/978-1-4614-0110-0_16 |
| [22] | Katoh, N.; Tanigawa, S-I, Fast enumeration algorithms for non-crossing geometric graphs, Discrete Comput. Geom., 42, 3, 443-468, 2009 · Zbl 1177.05119 · doi:10.1007/s00454-009-9164-4 |
| [23] | Lee, DT, Visibility of a simple polygon, CVGIP, 22, 2, 207-221, 1983 · Zbl 0532.68071 · doi:10.1016/0734-189x(83)90065-8 |
| [24] | Marx, D. and Miltzow, T.: Peeling and nibbling the cactus: subexponential-time algorithms for counting triangulations and related problems. In: Fekete., S. P. and Lubiw, A (eds) 32nd International Symposium on Computational Geometry, SoCG 2016, June 14-18, 2016, Boston, MA, USA, volume 51 of LIPIcs, pp. 52:1-52:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, (2016). doi:10.4230/LIPIcs.SoCG.2016.52 · Zbl 1387.68269 |
| [25] | Meisters, GH, Polygons have ears, Amer. Math. Mon., 82, 6, 648-651, 1975 · Zbl 0304.54038 · doi:10.2307/2319703 |
| [26] | Mitchell, JS; O’Rourke, J., Computational geometry column, Int. J. Comput. Geom. Appl., 11, 5, 573-582, 2001 · doi:10.1142/S0218195901000651 |
| [27] | OEIS contributors. Sequence A180562. The On-Line Encyclopedia of Integer Sequences, March 26 (2014). URL: https://oeis.org/A180562 |
| [28] | OEIS contributors. Sequence A238846. The On-Line Encyclopedia of Integer Sequences, November 24 (2021). URL: https://oeis.org/A238846 |
| [29] | OEIS contributors. Sequence A001792. The On-Line Encyclopedia of Integer Sequences, April 13 (2022). URL: https://oeis.org/A001792 |
| [30] | Quintas, LV; Supnick, F., On some properties of shortest Hamiltonian circuits, Amer. Math. Mon., 72, 9, 977-980, 1965 · Zbl 0134.40603 · doi:10.2307/2313333 |
| [31] | Razen, A.; Welzl, E.; Calude, CS; Rozenberg, G.; Salomaa, A., Counting plane graphs with exponential speed-up, Rainbow of Computer Science: dedicated to Hermann Maurer on the Occasion of His 70th Birthday, 36-46, 2011, New York: Springer, New York · Zbl 1277.05122 · doi:10.1007/978-3-642-19391-0_3 |
| [32] | Sharir, M.; Sheffer, A., Counting plane graphs: cross-graph charging schemes, Combin. Probab. Comput., 22, 6, 935-954, 2013 · Zbl 1282.05169 · doi:10.1017/S096354831300031X |
| [33] | Sharir, M.; Sheffer, A.; Welzl, E., Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn’s technique, J. Combin. Theory Ser. A, 120, 4, 777-794, 2013 · Zbl 1262.05035 · doi:10.1016/j.jcta.2013.01.002 |
| [34] | Steinhaus, H., One Hundred Problems in Elementary Mathematics, 17, 85-86, 1964, New York: Basic Books, New York · Zbl 1339.00001 |
| [35] | Tanigawa, S-I, Enumeration of non-crossing geometric graphs, Encyclopedia of Algorithms, 638-640, 2016, New York: Springer, New York · doi:10.1007/978-1-4939-2864-4_729 |
| [36] | Welzl, E.: Counting simple polygonizations of planar point sets. In: Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, Toronto, Ontario, Canada, August 10-12, (2011). https://www.cccg.ca/proceedings/2011/papers/invited3.pdf |
| [37] | Wettstein, M., Counting and enumerating crossing-free geometric graphs, J. Comput. Geom., 8, 1, 47-77, 2017 · Zbl 1393.68178 · doi:10.20382/jocg.v8i1a4 |
| [38] | Wu, RY; Chang, JM; Pai, KJ; Wang, YL, Amortized efficiency of generating planar paths in convex position, Theor. Comput. Sci., 412, 35, 4504-4512, 2011 · Zbl 1223.68088 · doi:10.1016/j.tcs.2011.04.017 |
| [39] | Yamanaka, K.; Avis, D.; Horiyama, T.; Okamoto, Y.; Uehara, R.; Yamauchi, T., Algorithmic enumeration of surrounding polygons, Discrete Appl. Math., 303, 305-313, 2021 · Zbl 1523.68136 · doi:10.1016/j.dam.2020.03.034 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
