Algorithmic enumeration of surrounding polygons. (English) Zbl 1523.68136
Summary: We are given a set \(S\) of points in the Euclidean plane. We assume that \(S\) is in general position. A simple polygon \(P\) is a surrounding polygon of \(S\) if each vertex of \(P\) is a point in \(S\) and every point in \(S\) is either inside \(P\) or a vertex of \(P\). In this paper, we present an enumeration algorithm of the surrounding polygons for a given point set. Our algorithm is based on reverse search by Avis and Fukuda and enumerates all the surrounding polygons in polynomial delay and quadratic space. It also provides the first space efficient method to generate all simple polygonizations on a given point set in exponential time. By relating these two problems we provide an upper bound on the number of surrounding polygons.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 05A15 | Exact enumeration problems, generating functions |
| 68R05 | Combinatorics in computer science |
| 68W05 | Nonnumerical algorithms |
Keywords:
polygons; surrounding polygons; simple polygonizations; enumeration algorithms; polynomial delayReferences:
| [1] | O. Aichholzer, http://www.ist.tugraz.at/staff/aichholzer/research/rp/triangulations/ordertypes/, 2006. |
| [2] | Aichholzer, O.; Aurenhammer, F.; Krasser, H., Enumerating order types for small point sets with applications, Order, 19, 3, 265-281 (2002) · Zbl 1027.68127 · doi:10.1023/A:1021231927255 |
| [3] | T. Auer, M. Held, Heuristics for the generation of random polygons, in: Proceedings of the 8th Canadian Conference on Computational Geometry, 1996, pp. 38-43. |
| [4] | Avis, D.; Fukuda, K., Reverse search for enumeration, Discrete Appl. Math., 65, 1-3, 21-46 (1996) · Zbl 0854.68070 |
| [5] | Bespamyatnikh, S., An efficient algorithm for enumeration of triangulations, Comput. Geom. Theory Appl., 23, 3, 271-279 (2002) · Zbl 1018.65029 |
| [6] | Chazelle, B.; Edelsbrunner, H.; Grigni, M.; Guibas, L. J.; Hershberger, J.; Sharir, M.; Snoeyink, J., Ray shooting in polygons using geodesic triangulations, Algorithmica, 12, 1, 54-68 (1994) · Zbl 0813.68158 |
| [7] | Chazelle, B.; Guibas, L. J., Visibility and intersection problems in plane geometry, Discrete Comput. Geom., 4, 551-581 (1989) · Zbl 0695.68033 |
| [8] | E.D. Demaine, http://erikdemaine.org/polygonization/, 2012. |
| [9] | García, A.; Noy, M.; Tejel, J., Lower bounds on the number of crossing-free subgraphs of \(K_N\), Comput. Geom., 16, 4, 211-221 (2000) · Zbl 0966.68158 |
| [10] | Goswami, P. P.; Das, S.; Nandy, S. C., Triangular range counting query in 2D and its application in finding \(k\) nearest neighbors of a line segment, Comput. Geom., 29, 3, 163-175 (2004) · Zbl 1060.65026 |
| [11] | Hernando, M. C.; Houle, M. E.; 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 |
| [12] | T. Horiyama, W. Shoji, Edge unfoldings of platonic solids never overlap, in: Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011, pp. 65-70. |
| [13] | Katoh, N.; Tanigawa, S., Enumerating edge-constrained triangulations and edge-constrained non-crossing geometric spanning trees, Discrete Appl. Math., 157, 17, 3569-3585 (2009) · Zbl 1227.05236 |
| [14] | Marx, D.; Miltzow, T., Peeling and nibbling the Cactus: Subexponential-time algorithms for counting triangulations and related problems, (32nd International Symposium on Computational Geometry, SoCG 2016, June 14-18, 2016, Boston, MA, USA (2016)), 52:1-52:16 · Zbl 1387.68269 · doi:10.4230/LIPIcs.SoCG.2016.52 |
| [15] | Meisters, G. H., Polygons have ears, Amer. Math. Monthly, 82, 6, 648-651 (1975) · Zbl 0304.54038 |
| [16] | Mitchell, J. S.B.; O’Rourke, J., Computational geometry column 42, Internat. J. Comput. Geom. Appl., 11, 5, 573-582 (2001) |
| [17] | Nakahata, Y.; Horiyama, T.; Minato, S.; Yamanaka, K., Compiling crossing-free geometric graphs with connectivity constraint for fast enumeration, random sampling, and optimization, CoRR, abs/2001.08899 (2020) |
| [18] | Nakano, S.; Uno, T., Generating colored trees, (Proceedings of the 31th Workshop on Graph-Theoretic Concepts in Computer Science, (WG 2005). Proceedings of the 31th Workshop on Graph-Theoretic Concepts in Computer Science, (WG 2005), LNCS 3787 (2005)), 249-260 · Zbl 1171.68633 |
| [19] | O’Rourke, J.; Suri, S.; Tóth, C. D., Polygons, (Handbook of Discrete and Computational Geometry (2017), Chapman and Hall/CRC), 787-810 · Zbl 1375.52001 |
| [20] | Sharir, M.; Sheffer, A.; Welzl, E., Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn’s technique, J. Comb. Theory Ser. A, 120, 4, 777-794 (2013) · Zbl 1262.05035 · doi:10.1016/j.jcta.2013.01.002 |
| [21] | C. Sohler, Generating random star-shaped polygons, in: Proceedings of the 11th Canadian Conference on Computational Geometry, 1999, pp. 174-177. |
| [22] | Teramoto, S.; Motoki, M.; Uehara, R.; Asano, T., Heuristics for Generating a Simple PolygonalizationIPSJ SIG Technical Report 2006-AL- 106(6), 41-48 (2006), Information Processing Society of Japan |
| [23] | Welzl, E., Counting simple polygonizations of planar point sets, (Proceedings of the 23rd Annual Canadian Conference on Computational Geometry (2011)) |
| [24] | Wettstein, M., Counting and enumerating crossing-free geometric graphs, J. Comput. Geom., 8, 1, 47-77 (2017) · Zbl 1393.68178 |
| [25] | K. Yamanaka, S. Nakano, Y. Matsui, R. Uehara, K. Nakada, Efficient enumeration of pseudoline arrangements, in: Proceedings of European Workshop on Computational Geometry, 2009, pp. 143-146. |
| [26] | Zhu, C.; Sundaram, G.; Snoeyink, J.; Mitchell, J. S.B., Generating random polygons with given vertices, Comput. Geom. Theory Appl., 6, 277-290 (1996) · Zbl 0857.68101 |
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.
