# 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
Full Text:
##### References:
  Aichholzer, O.; Aurenhammer, F.; Krasser, H., Enumerating order types for small point sets with applications, Order, 19, 3, 265-281 (2002) · Zbl 1027.68127  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  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  Aichholzer, O., Enumerating order types for small point sets with applications · Zbl 1027.68127  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  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  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  Bhattacharya, B. B.; Das, S., Disjoint empty convex pentagons in planar point sets, Period. Math. Hung., 66, 1, 73-86 (2013) · Zbl 1299.52022  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  Biere, A., PicoSAT essentials, J. Satisf. Boolean Model. Comput., 4, 75-97 (2008) · Zbl 1159.68403  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  Biniaz, A.; Maheshwari, A.; Smid, M. H.M., Compatible 4-holes in point sets (2017)  Balko, M.; Valtr, P., A SAT attack on the Erdős-Szekeres conjecture, Eur. J. Comb., 66, 13-23 (2017) · Zbl 1369.05063  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  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  Dumitrescu, A.; Tóth, G.; Pach, J., A note on blocking visibility between points, Geombinatorics, 19, 2, 67-73 (2009)  Edelsbrunner, H., Algorithms in Combinatorial Geometry (1987), Springer · Zbl 0634.52001  Erdős, P., Some more problems on elementary geometry, Aust. Math. Soc. Gaz., 5, 52-54 (1978) · Zbl 0417.52002  Erdős, P.; Szekeres, G., A combinatorial problem in geometry, Compos. Math., 2, 463-470 (1935) · JFM 61.0651.04  Felsner, S.; Goodman, J. E., Pseudoline arrangements, (Toth, O’Rourke; Goodman, Handbook of Discrete and Computational Geometry (2018), CRC Press) · Zbl 0914.51007  Felsner, S.; Sweeps, H. Weil, Arrangements and signotopes, Discrete Appl. Math., 109, 1, 67-94 (2001) · Zbl 0967.68159  Gerken, T., Empty convex hexagons in planar point sets, Discrete Comput. Geom., 39, 1, 239-272 (2008) · Zbl 1184.52016  Goodman, J. E.; Pollack, R., Multidimensional sorting, SIAM J. Comput., 12, 3, 484-507 (1983) · Zbl 0525.68038  Harborth, H., Konvexe Fünfecke in ebenen Punktmengen, Elem. Math., 33, 116-118 (1978), In German · Zbl 0397.52005  Horton, J., Sets with no empty convex 7-gons, Can. Math. Bull., 26, 482-484 (1983) · Zbl 0521.52010  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  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  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  Hosono, K.; Urabe, M., Specified holes with pairwise disjoint interiors in planar point sets, AKCE Int. J. Graphs Comb. (2018), in press  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  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  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  Matoušek, J., Convex independent subsets, (Lectures on Discrete Geometry (2002), Springer), 29-39  Nicolas, M. C., The empty hexagon theorem, Discrete Comput. Geom., 38, 2, 389-397 (2007) · Zbl 1146.52010  O’Rourke, J., Computational Geometry in C (1994), Cambridge University Press · Zbl 0816.68124  Overmars, M., Finding sets of points without empty convex 6-gons, Discrete Comput. Geom., 29, 1, 153-158 (2002) · Zbl 1019.52010  Pilz, A., A note on the flip distance problem for edge-labeled triangulations (2018)  Webpage, M. Scheucher, On disjoint holes in point sets  Schrijver, A., Combinatorial Optimization - Polyhedra and Efficiency (2003), Springer · Zbl 1041.90001  Scheucher, M., On Order Types, Projective Classes, and Realizations (2014), Graz University of Technology: Graz University of Technology Austria, Bachelor’s thesis  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.  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  Scheucher, M., Points, Lines, and Circles: Some Contributions to Combinatorial Geometry (2020), Technische Universität Berlin: Technische Universität Berlin Berlin, Doctoral thesis  Szekeres, G.; Peters, L., Computer solution to the 17-point Erdős-Szekeres problem, ANZIAM J., 48, 2, 151-164 (2006) · Zbl 1152.52008  Sakai, T.; Urrutia, J., Covering the convex quadrilaterals of point sets, Graphs Comb., 23, 1, 343-357 (2007) · Zbl 1118.52021  Suk, A., On the Erdős-Szekeres convex polygon problem, J. Am. Math. Soc., 30, 1047-1053 (2017) · Zbl 1370.52032  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  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  U. Wagner, E. Welzl, Connectivity of triangulation flip graphs in the plane, Unpublished manuscript.  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.