×

zbMATH — the first resource for mathematics

Two disjoint 5-holes in point sets. (English) Zbl 07290974
Summary: Given a set of points \(S \subseteq \mathbb{R}^2\), a subset \(X \subseteq S\) with \(| X | = k\) is called k-gon if all points of \(X\) lie on the boundary of the convex hull of \(X\), and k-hole if, in addition, no point of \(S \smallsetminus X\) lies in the convex hull of \(X\). We use computer assistance to show that every set of 17 points in general position admits two disjoint 5-holes, that is, holes with disjoint respective convex hulls. This answers a question of Hosono and Urabe (2001). We also provide new bounds for three and more pairwise disjoint holes.
In a recent article, Hosono and Urabe (2018) present new results on interior-disjoint holes – a variant, which also has been investigated in the last two decades. Using our program, we show that every set of 15 points contains two interior-disjoint 5-holes.
Moreover, our program can be used to verify that every set of 17 points contains a 6-gon within significantly smaller computation time than the original program by Szekeres and Peters (2006). Another independent verification of this result was done by Marić (2019).
MSC:
68U Computing methodologies and applications
52C Discrete geometry
68R Discrete mathematics in relation to computer science
Software:
DRAT-trim; PicoSAT
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aichholzer, O.; Aurenhammer, F.; Krasser, H., Enumerating order types for small point sets with applications, Order, 19, 3, 265-281 (2002) · Zbl 1027.68127
[2] Aichholzer, O.; Balko, M.; Hackl, T.; Kyncl, J.; Parada, I.; Scheucher, M.; Valtr, P.; Vogtenhuber, B., A superlinear lower bound on the number of 5-holes, (Aronov, B.; Katz, M. J., 33rd International Symposium on Computational Geometry. 33rd International Symposium on Computational Geometry, SoCG 2017. 33rd International Symposium on Computational Geometry. 33rd International Symposium on Computational Geometry, SoCG 2017, LIPIcs, vol. 77 (2017)), Article 8 pp. · Zbl 1432.52027
[3] Aichholzer, O.; Balko, M.; Hackl, T.; Kynčl, J.; Parada, I.; Scheucher, M.; Valtr, P.; Vogtenhuber, B., A superlinear lower bound on the number of 5-holes (2017) · Zbl 1432.52027
[4] Aichholzer, O., Enumerating order types for small point sets with applications · Zbl 1027.68127
[5] Aichholzer, O.; Krasser, H., Abstract order type extension and new results on the rectilinear crossing number, Comput. Geom. Theory Appl., 36, 1, 2-15 (2006) · Zbl 1110.65019
[6] Audemard, G.; Simon, L., Predicting learnt clauses quality in modern SAT solvers, (Proc. 21st International Joint Conference on Artificial Intelligence. Proc. 21st International Joint Conference on Artificial Intelligence, IJCAI 2009 (2009)), 399-404
[7] Bhattacharya, B. B.; Das, S., On the minimum size of a point set containing a 5-hole and a disjoint 4-hole, Studia Sci. Math. Hung., 48, 4, 445-457 (2011) · Zbl 1265.52017
[8] Bhattacharya, B. B.; Das, S., Disjoint empty convex pentagons in planar point sets, Period. Math. Hung., 66, 1, 73-86 (2013) · Zbl 1299.52022
[9] Balko, M.; Fulek, R.; Kynčl, J., Crossing numbers and combinatorial characterization of monotone drawings of \(K_n\), Discrete Comput. Geom., 53, 1, 107-143 (2015) · Zbl 1307.05058
[10] Biere, A., PicoSAT essentials, J. Satisf. Boolean Model. Comput., 4, 75-97 (2008) · Zbl 1159.68403
[11] Bárány, I.; Károlyi, G., Problems and results around the Erdös-Szekeres convex polygon theorem, (Proc. Japanese Conference on Discrete and Computational Geometry. Proc. Japanese Conference on Discrete and Computational Geometry, JCDCG 2000. Proc. Japanese Conference on Discrete and Computational Geometry. Proc. Japanese Conference on Discrete and Computational Geometry, JCDCG 2000, LNCS, vol. 2098 (2001), Springer), 91-105 · Zbl 0998.52004
[12] Biniaz, A.; Maheshwari, A.; Smid, M. H.M., Compatible 4-holes in point sets (2017)
[13] Balko, M.; Valtr, P., A SAT attack on the Erdős-Szekeres conjecture, Eur. J. Comb., 66, 13-23 (2017) · Zbl 1369.05063
[14] Cano, J.; García, A.; Hurtado, F.; Sakai, T.; Tejel, J.; Urrutia, J., Blocking the k-holes of point sets in the plane, Graphs Comb., 31, 5, 1271-1287 (2015) · Zbl 1321.05028
[15] Devillers, O.; Hurtado, F.; Károlyi, G.; Seara, C., Chromatic variants of the Erdős-Szekeres theorem on points in convex position, Comput. Geom., 26, 3, 193-208 (2003) · Zbl 1034.52014
[16] Dumitrescu, A.; Tóth, G.; Pach, J., A note on blocking visibility between points, Geombinatorics, 19, 2, 67-73 (2009)
[17] Edelsbrunner, H., Algorithms in Combinatorial Geometry (1987), Springer · Zbl 0634.52001
[18] Erdős, P., Some more problems on elementary geometry, Aust. Math. Soc. Gaz., 5, 52-54 (1978) · Zbl 0417.52002
[19] Erdős, P.; Szekeres, G., A combinatorial problem in geometry, Compos. Math., 2, 463-470 (1935) · JFM 61.0651.04
[20] Felsner, S.; Goodman, J. E., Pseudoline arrangements, (Toth, O’Rourke; Goodman, Handbook of Discrete and Computational Geometry (2018), CRC Press) · Zbl 0914.51007
[21] Felsner, S.; Sweeps, H. Weil, Arrangements and signotopes, Discrete Appl. Math., 109, 1, 67-94 (2001) · Zbl 0967.68159
[22] Gerken, T., Empty convex hexagons in planar point sets, Discrete Comput. Geom., 39, 1, 239-272 (2008) · Zbl 1184.52016
[23] Goodman, J. E.; Pollack, R., Multidimensional sorting, SIAM J. Comput., 12, 3, 484-507 (1983) · Zbl 0525.68038
[24] Harborth, H., Konvexe Fünfecke in ebenen Punktmengen, Elem. Math., 33, 116-118 (1978), In German · Zbl 0397.52005
[25] Horton, J., Sets with no empty convex 7-gons, Can. Math. Bull., 26, 482-484 (1983) · Zbl 0521.52010
[26] Hosono, K.; Urabe, M., On the number of disjoint convex quadrilaterals for a planar point set, Comput. Geom., 20, 3, 97-104 (2001) · Zbl 0990.68171
[27] Hosono, K.; Urabe, M., On the minimum size of a point set containing two non-intersecting empty convex polygons, (Proc. Japanese Conference on Discrete and Computational Geometry. Proc. Japanese Conference on Discrete and Computational Geometry, JCDCG 2004. Proc. Japanese Conference on Discrete and Computational Geometry. Proc. Japanese Conference on Discrete and Computational Geometry, JCDCG 2004, LNCS, vol. 3742 (2005), Springer), 117-122 · Zbl 1136.52311
[28] Hosono, K.; Urabe, M., A minimal planar point set with specified disjoint empty convex subsets, (Kyoto International Conference on Computational Geometry and Graph Theory. Kyoto International Conference on Computational Geometry and Graph Theory, KyotoCGGT 2007. Kyoto International Conference on Computational Geometry and Graph Theory. Kyoto International Conference on Computational Geometry and Graph Theory, KyotoCGGT 2007, LNCS, vol. 4535 (2008), Springer), 90-100 · Zbl 1162.52302
[29] Hosono, K.; Urabe, M., Specified holes with pairwise disjoint interiors in planar point sets, AKCE Int. J. Graphs Comb. (2018), in press
[30] Koshelev, V. A., On Erdős-Szekeres problem for empty hexagons in the plane, Model. Anal. Inf. Sist., 16, 2, 22-74 (2009), In Russian
[31] Krasser, H., Order Types of Point Sets in the Plane (2003), Institute for Theoretical Computer Science, Graz University of Technology: Institute for Theoretical Computer Science, Graz University of Technology Austria, PhD thesis
[32] Marić, F., Fast formal proof of the Erdős-Szekeres conjecture for convex polygons with at most 6 points, J. Autom. Reason., 62, 301-329 (2019) · Zbl 07038739
[33] Matoušek, J., Convex independent subsets, (Lectures on Discrete Geometry (2002), Springer), 29-39
[34] Nicolas, M. C., The empty hexagon theorem, Discrete Comput. Geom., 38, 2, 389-397 (2007) · Zbl 1146.52010
[35] O’Rourke, J., Computational Geometry in C (1994), Cambridge University Press · Zbl 0816.68124
[36] Overmars, M., Finding sets of points without empty convex 6-gons, Discrete Comput. Geom., 29, 1, 153-158 (2002) · Zbl 1019.52010
[37] Pilz, A., A note on the flip distance problem for edge-labeled triangulations (2018)
[38] Webpage, M. Scheucher, On disjoint holes in point sets
[39] Schrijver, A., Combinatorial Optimization - Polyhedra and Efficiency (2003), Springer · Zbl 1041.90001
[40] Scheucher, M., On Order Types, Projective Classes, and Realizations (2014), Graz University of Technology: Graz University of Technology Austria, Bachelor’s thesis
[41] Scheucher, M., On disjoint holes in point sets, (Proc. 35th European Workshop on Computational Geometry. Proc. 35th European Workshop on Computational Geometry, EuroCG’19 (2019)), Article 22 pp.
[42] Scheucher, M., On disjoint holes in point sets, (Proc. of the European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB’19), Vol. 88, No. 3 (2019)), 1049-1056
[43] Scheucher, M., Points, Lines, and Circles: Some Contributions to Combinatorial Geometry (2020), Technische Universität Berlin: Technische Universität Berlin Berlin, Doctoral thesis
[44] Szekeres, G.; Peters, L., Computer solution to the 17-point Erdős-Szekeres problem, ANZIAM J., 48, 2, 151-164 (2006) · Zbl 1152.52008
[45] Sakai, T.; Urrutia, J., Covering the convex quadrilaterals of point sets, Graphs Comb., 23, 1, 343-357 (2007) · Zbl 1118.52021
[46] Suk, A., On the Erdős-Szekeres convex polygon problem, J. Am. Math. Soc., 30, 1047-1053 (2017) · Zbl 1370.52032
[47] Valtr, P., On empty hexagons, (Surveys on Discrete and Computational Geometry: Twenty Years Later. Surveys on Discrete and Computational Geometry: Twenty Years Later, Contemporary Mathematics, vol. 453 (2008), AMS), 433-441 · Zbl 1147.52301
[48] Wetzler, N.; Heule, M. J.H.; Hunt, W. A., DRAT-trim: efficient checking and trimming using expressive clausal proofs, (Sinz, C.; Egly, U., Theory and Applications of Satisfiability Testing - SAT 2014 (2014), Springer), 422-429 · Zbl 1423.68475
[49] U. Wagner, E. Welzl, Connectivity of triangulation flip graphs in the plane, Unpublished manuscript.
[50] You, X. S.; Wei, X. L., On the minimum size of a point set containing a 5-hole and double disjoint 3-holes, Math. Notes, 97, 5, 951-960 (2015) · Zbl 1331.52025
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.