Document

**Published in:** LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Given a set S ⊆ ℝ², define the Helly number of S, denoted by H(S), as the smallest positive integer N, if it exists, for which the following statement is true: for any finite family ℱ of convex sets in ℝ² such that the intersection of any N or fewer members of ℱ contains at least one point of S, there is a point of S common to all members of ℱ.
We prove that the Helly numbers of exponential lattices {αⁿ : n ∈ ℕ₀}² are finite for every α > 1 and we determine their exact values in some instances. In particular, we obtain H({2ⁿ : n ∈ ℕ₀}²) = 5, solving a problem posed by Dillon (2021).
For real numbers α, β > 1, we also fully characterize exponential lattices L(α,β) = {αⁿ : n ∈ ℕ₀} × {βⁿ : n ∈ ℕ₀} with finite Helly numbers by showing that H(L(α,β)) is finite if and only if log_α(β) is rational.

Gergely Ambrus, Martin Balko, Nóra Frankl, Attila Jung, and Márton Naszódi. On Helly Numbers of Exponential Lattices. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ambrus_et_al:LIPIcs.SoCG.2023.8, author = {Ambrus, Gergely and Balko, Martin and Frankl, N\'{o}ra and Jung, Attila and Nasz\'{o}di, M\'{a}rton}, title = {{On Helly Numbers of Exponential Lattices}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {8:1--8:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-273-0}, ISSN = {1868-8969}, year = {2023}, volume = {258}, editor = {Chambers, Erin W. and Gudmundsson, Joachim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.8}, URN = {urn:nbn:de:0030-drops-178584}, doi = {10.4230/LIPIcs.SoCG.2023.8}, annote = {Keywords: Helly numbers, exponential lattices, Diophantine approximation} }

Document

**Published in:** LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

An obstacle representation of a graph G consists of a set of pairwise disjoint simply-connected closed regions and a one-to-one mapping of the vertices of G to points such that two vertices are adjacent in G if and only if the line segment connecting the two corresponding points does not intersect any obstacle. The obstacle number of a graph is the smallest number of obstacles in an obstacle representation of the graph in the plane such that all obstacles are simple polygons.
It is known that the obstacle number of each n-vertex graph is O(n log n) [Balko, Cibulka, and Valtr, 2018] and that there are n-vertex graphs whose obstacle number is Ω(n/(log log n)²) [Dujmović and Morin, 2015]. We improve this lower bound to Ω(n/log log n) for simple polygons and to Ω(n) for convex polygons. To obtain these stronger bounds, we improve known estimates on the number of n-vertex graphs with bounded obstacle number, solving a conjecture by Dujmović and Morin. We also show that if the drawing of some n-vertex graph is given as part of the input, then for some drawings Ω(n²) obstacles are required to turn them into an obstacle representation of the graph. Our bounds are asymptotically tight in several instances.
We complement these combinatorial bounds by two complexity results. First, we show that computing the obstacle number of a graph G is fixed-parameter tractable in the vertex cover number of G. Second, we show that, given a graph G and a simple polygon P, it is NP-hard to decide whether G admits an obstacle representation using P as the only obstacle.

Martin Balko, Steven Chaplick, Robert Ganian, Siddharth Gupta, Michael Hoffmann, Pavel Valtr, and Alexander Wolff. Bounding and Computing Obstacle Numbers of Graphs. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{balko_et_al:LIPIcs.ESA.2022.11, author = {Balko, Martin and Chaplick, Steven and Ganian, Robert and Gupta, Siddharth and Hoffmann, Michael and Valtr, Pavel and Wolff, Alexander}, title = {{Bounding and Computing Obstacle Numbers of Graphs}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {11:1--11:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.11}, URN = {urn:nbn:de:0030-drops-169495}, doi = {10.4230/LIPIcs.ESA.2022.11}, annote = {Keywords: Obstacle representation, Obstacle number, Visibility, NP-hardness, FPT} }

Document

**Published in:** LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

We consider point sets in the real projective plane ℝ𝒫² and explore variants of classical extremal problems about planar point sets in this setting, with a main focus on Erdős-Szekeres-type problems.
We provide asymptotically tight bounds for a variant of the Erdős-Szekeres theorem about point sets in convex position in ℝ𝒫², which was initiated by Harborth and Möller in 1994. The notion of convex position in ℝ𝒫² agrees with the definition of convex sets introduced by Steinitz in 1913.
For k ≥ 3, an (affine) k-hole in a finite set S ⊆ ℝ² is a set of k points from S in convex position with no point of S in the interior of their convex hull. After introducing a new notion of k-holes for points sets from ℝ𝒫², called projective k-holes, we find arbitrarily large finite sets of points from ℝ𝒫² with no projective 8-holes, providing an analogue of a classical result by Horton from 1983. We also prove that they contain only quadratically many projective k-holes for k ≤ 7. On the other hand, we show that the number of k-holes can be substantially larger in ℝ𝒫² than in ℝ² by constructing, for every k ∈ {3,… ,6}, sets of n points from ℝ² ⊂ ℝ𝒫² with Ω(n^{3-3/5k}) projective k-holes and only O(n²) affine k-holes. Last but not least, we prove several other results, for example about projective holes in random point sets in ℝ𝒫² and about some algorithmic aspects.
The study of extremal problems about point sets in ℝ𝒫² opens a new area of research, which we support by posing several open problems.

Martin Balko, Manfred Scheucher, and Pavel Valtr. Erdős-Szekeres-Type Problems in the Real Projective Plane. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{balko_et_al:LIPIcs.SoCG.2022.10, author = {Balko, Martin and Scheucher, Manfred and Valtr, Pavel}, title = {{Erd\H{o}s-Szekeres-Type Problems in the Real Projective Plane}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {10:1--10:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-227-3}, ISSN = {1868-8969}, year = {2022}, volume = {224}, editor = {Goaoc, Xavier and Kerber, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.10}, URN = {urn:nbn:de:0030-drops-160182}, doi = {10.4230/LIPIcs.SoCG.2022.10}, annote = {Keywords: real projective plane, point set, convex position, k-gon, k-hole, Erd\H{o}s-Szekeres theorem, Horton set, random point set} }

Document

**Published in:** LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

For d ∈ ℕ, let S be a finite set of points in ℝ^d in general position. A set H of k points from S is a k-hole in S if all points from H lie on the boundary of the convex hull conv(H) of H and the interior of conv(H) does not contain any point from S. A set I of k points from S is a k-island in S if conv(I) ∩ S = I. Note that each k-hole in S is a k-island in S.
For fixed positive integers d, k and a convex body K in ℝ^d with d-dimensional Lebesgue measure 1, let S be a set of n points chosen uniformly and independently at random from K. We show that the expected number of k-islands in S is in O(n^d). In the case k=d+1, we prove that the expected number of empty simplices (that is, (d+1)-holes) in S is at most 2^(d-1) ⋅ d! ⋅ binom(n,d). Our results improve and generalize previous bounds by Bárány and Füredi [I. Bárány and Z. Füredi, 1987], Valtr [P. Valtr, 1995], Fabila-Monroy and Huemer [Fabila-Monroy and Huemer, 2012], and Fabila-Monroy, Huemer, and Mitsche [Fabila-Monroy et al., 2015].

Martin Balko, Manfred Scheucher, and Pavel Valtr. Holes and Islands in Random Point Sets. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{balko_et_al:LIPIcs.SoCG.2020.14, author = {Balko, Martin and Scheucher, Manfred and Valtr, Pavel}, title = {{Holes and Islands in Random Point Sets}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {14:1--14:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-143-6}, ISSN = {1868-8969}, year = {2020}, volume = {164}, editor = {Cabello, Sergio and Chen, Danny Z.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.14}, URN = {urn:nbn:de:0030-drops-121722}, doi = {10.4230/LIPIcs.SoCG.2020.14}, annote = {Keywords: stochastic geometry, random point set, Erd\H{o}s-Szekeres type problem, k-hole, k-island, empty polytope, convex position, Horton set} }

Document

**Published in:** LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Let P be a finite set of points in the plane in general position, that is, no three points of P are on a common line. We say that a set H of five points from P is a 5-hole in P if H is the vertex set of a convex 5-gon containing no other points of P. For a positive integer n, let h_5(n) be the minimum number of 5-holes among all sets of n points in the plane in general position.
Despite many efforts in the last 30 years, the best known asymptotic lower and upper bounds for h_5(n) have been of order Omega(n) and O(n^2), respectively. We show that h_5(n) = Omega(n(log n)^(4/5)), obtaining the first superlinear lower bound on h_5(n).
The following structural result, which might be of independent interest, is a crucial step in the proof of this lower bound. If a finite set P of points in the plane in general position is partitioned by a line l into two subsets, each of size at least 5 and not in convex position, then l intersects the convex hull of some 5-hole in P. The proof of this result is computer-assisted.

Oswin Aichholzer, Martin Balko, Thomas Hackl, Jan Kyncl, Irene Parada, Manfred Scheucher, Pavel Valtr, and Birgit Vogtenhuber. A Superlinear Lower Bound on the Number of 5-Holes. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{aichholzer_et_al:LIPIcs.SoCG.2017.8, author = {Aichholzer, Oswin and Balko, Martin and Hackl, Thomas and Kyncl, Jan and Parada, Irene and Scheucher, Manfred and Valtr, Pavel and Vogtenhuber, Birgit}, title = {{A Superlinear Lower Bound on the Number of 5-Holes}}, booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)}, pages = {8:1--8:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-038-5}, ISSN = {1868-8969}, year = {2017}, volume = {77}, editor = {Aronov, Boris and Katz, Matthew J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.8}, URN = {urn:nbn:de:0030-drops-72008}, doi = {10.4230/LIPIcs.SoCG.2017.8}, annote = {Keywords: Erd\"{o}s-Szekeres type problem, k-hole, empty k-gon, empty pentagon, planar point set} }

Document

**Published in:** LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Let d and k be integers with 1 <= k <= d-1. Let Lambda be a d-dimensional lattice and let K be a d-dimensional compact convex body symmetric about the origin. We provide estimates for the minimum number of k-dimensional linear subspaces needed to cover all points in the intersection of Lambda with K. In particular, our results imply that the minimum number of k-dimensional linear subspaces needed to cover the d-dimensional n * ... * n grid is at least Omega(n^(d(d-k)/(d-1)-epsilon)) and at most O(n^(d(d-k)/(d-1))), where epsilon > 0 is an arbitrarily small constant. This nearly settles a problem mentioned in the book of Brass, Moser, and Pach. We also find tight bounds for the minimum number of k-dimensional affine subspaces needed to cover the intersection of Lambda with K.
We use these new results to improve the best known lower bound for the maximum number of point-hyperplane incidences by Brass and Knauer. For d > =3 and epsilon in (0,1), we show that there is an integer r=r(d,epsilon) such that for all positive integers n, m the following statement is true. There is a set of n points in R^d and an arrangement of m hyperplanes in R^d with no K_(r,r) in their incidence graph and with at least Omega((mn)^(1-(2d+3)/((d+2)(d+3)) - epsilon)) incidences if d is odd and Omega((mn)^(1-(2d^2+d-2)/((d+2)(d^2+2d-2)) - epsilon)) incidences if d is even.

Martin Balko, Josef Cibulka, and Pavel Valtr. Covering Lattice Points by Subspaces and Counting Point-Hyperplane Incidences. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{balko_et_al:LIPIcs.SoCG.2017.12, author = {Balko, Martin and Cibulka, Josef and Valtr, Pavel}, title = {{Covering Lattice Points by Subspaces and Counting Point-Hyperplane Incidences}}, booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)}, pages = {12:1--12:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-038-5}, ISSN = {1868-8969}, year = {2017}, volume = {77}, editor = {Aronov, Boris and Katz, Matthew J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.12}, URN = {urn:nbn:de:0030-drops-71955}, doi = {10.4230/LIPIcs.SoCG.2017.12}, annote = {Keywords: lattice point, covering, linear subspace, point-hyperplane incidence} }

Document

**Published in:** LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Let S be a subset of R^d with finite positive Lebesgue measure. The Beer index of convexity b(S) of S is the probability that two points of S chosen uniformly independently at random see each other in S. The convexity ratio c(S) of S is the Lebesgue measure of the largest convex subset of S divided by the Lebesgue measure of S. We investigate a relationship between these two natural measures of convexity of S.
We show that every subset S of the plane with simply connected components satisfies b(S) <= alpha c(S) for an absolute constant alpha, provided b(S) is defined. This implies an affirmative answer to the conjecture of Cabello et al. asserting that this estimate holds for simple polygons.
We also consider higher-order generalizations of b(S). For 1 <= k <= d, the k-index of convexity b_k(S) of a subset S of R^d is the probability that the convex hull of a (k+1)-tuple of points chosen uniformly independently at random from S is contained in S. We show that for every d >= 2 there is a constant beta(d) > 0 such that every subset S of R^d satisfies b_d(S) <= beta c(S), provided b_d(S) exists. We provide an almost matching lower bound by showing that there is a constant gamma(d) > 0 such that for every epsilon from (0,1] there is a subset S of R^d of Lebesgue measure one satisfying c(S) <= epsilon and b_d(S) >= (gamma epsilon)/log_2(1/epsilon) >= (gamma c(S))/log_2(1/c(S)).

Martin Balko, Vít Jelínek, Pavel Valtr, and Bartosz Walczak. On the Beer Index of Convexity and Its Variants. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 406-420, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{balko_et_al:LIPIcs.SOCG.2015.406, author = {Balko, Martin and Jel{\'\i}nek, V{\'\i}t and Valtr, Pavel and Walczak, Bartosz}, title = {{On the Beer Index of Convexity and Its Variants}}, booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)}, pages = {406--420}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-83-5}, ISSN = {1868-8969}, year = {2015}, volume = {34}, editor = {Arge, Lars and Pach, J\'{a}nos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.406}, URN = {urn:nbn:de:0030-drops-51229}, doi = {10.4230/LIPIcs.SOCG.2015.406}, annote = {Keywords: Beer index of convexity, convexity ratio, convexity measure, visibility} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail