Search Results

Documents authored by Smorodinsky, Shakhar

Document
DOI: 10.4230/LIPIcs.SoCG.2024.66
Zarankiewicz’s Problem via ε-t-Nets

Authors: Chaya Keller and Shakhar Smorodinsky

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
The classical Zarankiewicz’s problem asks for the maximum number of edges in a bipartite graph on n vertices which does not contain the complete bipartite graph K_{t,t}. Kővári, Sós and Turán proved an upper bound of O(n^{2-1/t}). Fox et al. obtained an improved bound of O(n^{2-1/d}) for graphs of VC-dimension d (where d < t). Basit, Chernikov, Starchenko, Tao and Tran improved the bound for the case of semilinear graphs. Chan and Har-Peled further improved Basit et al.’s bounds and presented (quasi-)linear upper bounds for several classes of geometrically-defined incidence graphs, including a bound of O(n log log n) for the incidence graph of points and pseudo-discs in the plane. In this paper we present a new approach to Zarankiewicz’s problem, via ε-t-nets - a recently introduced generalization of the classical notion of ε-nets. Using the new approach, we obtain a sharp bound of O(n) for the intersection graph of two families of pseudo-discs, thus both improving and generalizing the result of Chan and Har-Peled from incidence graphs to intersection graphs. We also obtain a short proof of the O(n^{2-1/d}) bound of Fox et al., and show improved bounds for several other classes of geometric intersection graphs, including a sharp O(n {log n}/{log log n}) bound for the intersection graph of two families of axis-parallel rectangles.
Cite as

Chaya Keller and Shakhar Smorodinsky. Zarankiewicz’s Problem via ε-t-Nets. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 66:1-66:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{keller_et_al:LIPIcs.SoCG.2024.66,
  author =	{Keller, Chaya and Smorodinsky, Shakhar},
  title =	{{Zarankiewicz’s Problem via \epsilon-t-Nets}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{66:1--66:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.66},
  URN =		{urn:nbn:de:0030-drops-200111},
  doi =		{10.4230/LIPIcs.SoCG.2024.66},
  annote =	{Keywords: Zarankiewicz’s Problem, \epsilon-t-nets, pseudo-discs, VC-dimension}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.33
A Solution to Ringel’s Circle Problem

Authors: James Davies, Chaya Keller, Linda Kleist, Shakhar Smorodinsky, and Bartosz Walczak

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

Abstract
We construct families of circles in the plane such that their tangency graphs have arbitrarily large girth and chromatic number. This provides a strong negative answer to Ringel’s circle problem (1959). The proof relies on a (multidimensional) version of Gallai’s theorem with polynomial constraints, which we derive from the Hales-Jewett theorem and which may be of independent interest.
Cite as

James Davies, Chaya Keller, Linda Kleist, Shakhar Smorodinsky, and Bartosz Walczak. A Solution to Ringel’s Circle Problem. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{davies_et_al:LIPIcs.SoCG.2022.33,
  author =	{Davies, James and Keller, Chaya and Kleist, Linda and Smorodinsky, Shakhar and Walczak, Bartosz},
  title =	{{A Solution to Ringel’s Circle Problem}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{33:1--33:14},
  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.33},
  URN =		{urn:nbn:de:0030-drops-160413},
  doi =		{10.4230/LIPIcs.SoCG.2022.33},
  annote =	{Keywords: circle arrangement, chromatic number, Gallai’s theorem, polynomial method}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.5
The ε-t-Net Problem

Authors: Noga Alon, Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, and Yelena Yuditsky

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

Abstract
We study a natural generalization of the classical ε-net problem (Haussler - Welzl 1987), which we call the ε-t-net problem: Given a hypergraph on n vertices and parameters t and ε ≥ t/n, find a minimum-sized family S of t-element subsets of vertices such that each hyperedge of size at least ε n contains a set in S. When t=1, this corresponds to the ε-net problem. We prove that any sufficiently large hypergraph with VC-dimension d admits an ε-t-net of size O((1+log t)d/ε log 1/ε). For some families of geometrically-defined hypergraphs (such as the dual hypergraph of regions with linear union complexity), we prove the existence of O(1/ε)-sized ε-t-nets. We also present an explicit construction of ε-t-nets (including ε-nets) for hypergraphs with bounded VC-dimension. In comparison to previous constructions for the special case of ε-nets (i.e., for t=1), it does not rely on advanced derandomization techniques. To this end we introduce a variant of the notion of VC-dimension which is of independent interest.
Cite as

Noga Alon, Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, and Yelena Yuditsky. The ε-t-Net Problem. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{alon_et_al:LIPIcs.SoCG.2020.5,
  author =	{Alon, Noga and Jartoux, Bruno and Keller, Chaya and Smorodinsky, Shakhar and Yuditsky, Yelena},
  title =	{{The \epsilon-t-Net Problem}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{5:1--5:15},
  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.5},
  URN =		{urn:nbn:de:0030-drops-121639},
  doi =		{10.4230/LIPIcs.SoCG.2020.5},
  annote =	{Keywords: epsilon-nets, geometric hypergraphs, VC-dimension, linear union complexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.2
Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs

Authors: A. Karim Abu-Affash, Paz Carmi, Anil Maheshwari, Pat Morin, Michiel Smid, and Shakhar Smorodinsky

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
We consider a well studied generalization of the maximum clique problem which is defined as follows. Given a graph G on n vertices and an integer d >= 1, in the maximum diameter-bounded subgraph problem (MaxDBS for short), the goal is to find a (vertex) maximum subgraph of G of diameter at most d. For d=1, this problem is equivalent to the maximum clique problem and thus it is NP-hard to approximate it within a factor n^{1-epsilon}, for any epsilon > 0. Moreover, it is known that, for any d >= 2, it is NP-hard to approximate MaxDBS within a factor n^{1/2 - epsilon}, for any epsilon > 0. In this paper we focus on MaxDBS for the class of unit disk graphs. We provide a polynomial-time constant-factor approximation algorithm for the problem. The approximation ratio of our algorithm does not depend on the diameter d. Even though the algorithm itself is simple, its analysis is rather involved. We combine tools from the theory of hypergraphs with bounded VC-dimension, k-quasi planar graphs, fractional Helly theorems and several geometric properties of unit disk graphs.
Cite as

A. Karim Abu-Affash, Paz Carmi, Anil Maheshwari, Pat Morin, Michiel Smid, and Shakhar Smorodinsky. Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{abuaffash_et_al:LIPIcs.SoCG.2018.2,
  author =	{Abu-Affash, A. Karim and Carmi, Paz and Maheshwari, Anil and Morin, Pat and Smid, Michiel and Smorodinsky, Shakhar},
  title =	{{Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{2:1--2:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.2},
  URN =		{urn:nbn:de:0030-drops-87152},
  doi =		{10.4230/LIPIcs.SoCG.2018.2},
  annote =	{Keywords: Approximation algorithms, maximum diameter-bounded subgraph, unit disk graphs, fractional Helly theorem, VC-dimension}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.51
From a (p,2)-Theorem to a Tight (p,q)-Theorem

Authors: Chaya Keller and Shakhar Smorodinsky

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
A family F of sets is said to satisfy the (p,q)-property if among any p sets of F some q have a non-empty intersection. The celebrated (p,q)-theorem of Alon and Kleitman asserts that any family of compact convex sets in R^d that satisfies the (p,q)-property for some q >= d+1, can be pierced by a fixed number (independent on the size of the family) f_d(p,q) of points. The minimum such piercing number is denoted by {HD}_d(p,q). Already in 1957, Hadwiger and Debrunner showed that whenever q > (d-1)/d p+1 the piercing number is {HD}_d(p,q)=p-q+1; no exact values of {HD}_d(p,q) were found ever since. While for an arbitrary family of compact convex sets in R^d, d >= 2, a (p,2)-property does not imply a bounded piercing number, such bounds were proved for numerous specific families. The best-studied among them is axis-parallel boxes in R^d, and specifically, axis-parallel rectangles in the plane. Wegner (1965) and (independently) Dol'nikov (1972) used a (p,2)-theorem for axis-parallel rectangles to show that {HD}_{rect}(p,q)=p-q+1 holds for all q>sqrt{2p}. These are the only values of q for which {HD}_{rect}(p,q) is known exactly. In this paper we present a general method which allows using a (p,2)-theorem as a bootstrapping to obtain a tight (p,q)-theorem, for families with Helly number 2, even without assuming that the sets in the family are convex or compact. To demonstrate the strength of this method, we show that {HD}_{d-box}(p,q)=p-q+1 holds for all q > c' log^{d-1} p, and in particular, {HD}_{rect}(p,q)=p-q+1 holds for all q >= 7 log_2 p (compared to q >= sqrt{2p}, obtained by Wegner and Dol'nikov more than 40 years ago). In addition, for several classes of families, we present improved (p,2)-theorems, some of which can be used as a bootstrapping to obtain tight (p,q)-theorems. In particular, we show that any family F of compact convex sets in R^d with Helly number 2 admits a (p,2)-theorem with piercing number O(p^{2d-1}), and thus, satisfies {HD}_{F}(p,q)=p-q+1 for all q>cp^{1-1/(2d-1)}, for a universal constant c.
Cite as

Chaya Keller and Shakhar Smorodinsky. From a (p,2)-Theorem to a Tight (p,q)-Theorem. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{keller_et_al:LIPIcs.SoCG.2018.51,
  author =	{Keller, Chaya and Smorodinsky, Shakhar},
  title =	{{From a (p,2)-Theorem to a Tight (p,q)-Theorem}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{51:1--51:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.51},
  URN =		{urn:nbn:de:0030-drops-87640},
  doi =		{10.4230/LIPIcs.SoCG.2018.51},
  annote =	{Keywords: (p,q)-Theorem, convexity, transversals, (p,2)-theorem, axis-parallel rectangles}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.34
On Interference Among Moving Sensors and Related Problems

Authors: Jean-Lou De Carufel, Matthew J. Katz, Matias Korman, André van Renssen, Marcel Roeloffzen, and Shakhar Smorodinsky

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
We show that for any set of n moving points in R^d and any parameter 2<=k<n, one can select a fixed non-empty subset of the points of size O(k log k), such that the Voronoi diagram of this subset is "balanced" at any given time (i.e., it contains O(n/k) points per cell). We also show that the bound O(k log k) is near optimal even for the one dimensional case in which points move linearly in time. As an application, we show that one can assign communication radii to the sensors of a network of $n$ moving sensors so that at any given time, their interference is O( (n log n)^0.5). This is optimal up to an O((log n)^0.5) factor.
Cite as

Jean-Lou De Carufel, Matthew J. Katz, Matias Korman, André van Renssen, Marcel Roeloffzen, and Shakhar Smorodinsky. On Interference Among Moving Sensors and Related Problems. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 34:1-34:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{decarufel_et_al:LIPIcs.ESA.2016.34,
  author =	{De Carufel, Jean-Lou and Katz, Matthew J. and Korman, Matias and van Renssen, Andr\'{e} and Roeloffzen, Marcel and Smorodinsky, Shakhar},
  title =	{{On Interference Among Moving Sensors and Related Problems}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{34:1--34:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.34},
  URN =		{urn:nbn:de:0030-drops-63850},
  doi =		{10.4230/LIPIcs.ESA.2016.34},
  annote =	{Keywords: Range spaces, Voronoi diagrams, moving points, facility location, interference minimization}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.59
Weak 1/r-Nets for Moving Points

Authors: Alexandre Rok and Shakhar Smorodinsky

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
In this paper, we extend the weak 1/r-net theorem to a kinetic setting where the underlying set of points is moving polynomially with bounded description complexity. We establish that one can find a kinetic analog N of a weak 1/r-net of cardinality O(r^(d(d+1)/2)log^d r) whose points are moving with coordinates that are rational functions with bounded description complexity. Moreover, each member of N has one polynomial coordinate.
Cite as

Alexandre Rok and Shakhar Smorodinsky. Weak 1/r-Nets for Moving Points. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 59:1-59:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{rok_et_al:LIPIcs.SoCG.2016.59,
  author =	{Rok, Alexandre and Smorodinsky, Shakhar},
  title =	{{Weak 1/r-Nets for Moving Points}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{59:1--59:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.59},
  URN =		{urn:nbn:de:0030-drops-59514},
  doi =		{10.4230/LIPIcs.SoCG.2016.59},
  annote =	{Keywords: Hypergraphs, Weak epsilon-net}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact