Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

The \(\varepsilon \)-t-Net Problem

  • Published:
Discrete & Computational Geometry Aims and scope Submit manuscript

Abstract

We study a natural generalization of the classical \(\varepsilon \)-net problem (Haussler and Welzl in Discrete Comput. Geom. 2(2), 127–151 (1987)), which we call the \(\varepsilon \)–t-net problem: Given a hypergraph on n vertices and parameters t and \(\varepsilon \ge t/n\), find a minimum-sized family S of t-element subsets of vertices such that each hyperedge of size at least \(\varepsilon n\) contains a set in S. When \(t=1\), this corresponds to the \(\varepsilon \)-net problem. We prove that any sufficiently large hypergraph with VC-dimension d admits an \(\varepsilon \)–t-net of size \(O(({d(1+\log t)}/{\varepsilon })\log (1/\varepsilon ))\). 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}/{\varepsilon })\)-sized \(\varepsilon \)–t-nets. We also present an explicit construction of \(\varepsilon \)–t-nets (including \(\varepsilon \)-nets) for hypergraphs with bounded VC-dimension. In comparison to previous constructions for the special case of \(\varepsilon \)-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. Finally, we use our techniques to generalize the notion of \(\varepsilon \)-approximation and to prove the existence of small-sized \(\varepsilon \)–t-approximations for sufficiently large hypergraphs with a bounded VC-dimension.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

Data Availability

Data sharing is not applicable to this article as no datasets were generated or analyzed during the current study.

References

  1. Ackerman, E., Keszegh, B., Pálvölgyi, D.: Coloring Delaunay-edges and their generalizations. Comput. Geom. 96, # 101745 (2021)

  2. Ackerman, E., Pinchasi, R.: On coloring points with respect to rectangles. J. Combin. Theory Ser. A 120(4), 811–815 (2013)

    Article  MathSciNet  Google Scholar 

  3. Agarwal, P.K., Pach, J., Sharir, M.: State of the union (of geometric objects). In: Surveys on Discrete and Computational Geometry (Snowbird 2006). Contemp. Math., vol. 453, pp. 9–48. American Mathematical Society, Providence (2008)

  4. Alon, N., Brightwell, G., Kierstead, H.A., Kostochka, A.V., Winkler, P.: Dominating sets in \(k\)-majority tournaments. J. Combin. Theory Ser. B 96(3), 374–387 (2006)

    Article  MathSciNet  Google Scholar 

  5. Aronov, B., Donakonda, A., Ezra, E., Pinchasi, R.: On pseudo-disk hypergraphs. Comput. Geom. 92, # 101687 (2021)

  6. Aronov, B., Ezra, E., Sharir, M.: Small-size \(\varepsilon \)-nets for axis-parallel rectangles and boxes. SIAM J. Comput. 39(7), 3248–3282 (2010)

    Article  MathSciNet  Google Scholar 

  7. Arya, S., da Fonseca, G.D., Mount, D.M.: Approximate polytope membership queries. SIAM J. Comput. 47(1), 1–51 (2018)

    Article  MathSciNet  Google Scholar 

  8. Assouad, P.: Densité et dimension. Ann. Inst. Fourier (Grenoble) 33(3), 233–282 (1983)

    Article  MathSciNet  Google Scholar 

  9. Beimel, A.: Secret-sharing schemes: a survey. In: Coding and Cryptology (Qingdao 2011). Lecture Notes in Comput. Sci., vol. 6639, pp. 11–46. Springer, Heidelberg (2011)

  10. Blumer, A., Ehrenfeucht, A., Haussler, D., Warmuth, M.K.: Learnability and the Vapnik–Chervonenkis dimension. J. Assoc. Comput. Mach. 36(4), 929–965 (1989)

    Article  MathSciNet  Google Scholar 

  11. Brönnimann, H., Chazelle, B., Matoušek, J.: Product range spaces, sensitive sampling, and derandomization. SIAM J. Comput. 28(5), 1552–1575 (1999)

    Article  MathSciNet  Google Scholar 

  12. Brönnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom. 14(4), 463–479 (1995)

    Article  MathSciNet  Google Scholar 

  13. Calabro, Ch.: The Exponential Complexity of Satisfiability Problems. PhD thesis, University of California, San Diego (2009). https://escholarship.org/uc/item/0pk5w64k

  14. Chan, T.M.: Improved deterministic algorithms for linear programming in low dimensions. ACM Trans. Algorithms 14(3), # 30 (2018)

  15. Chazelle, B., Matoušek, J.: On linear-time deterministic algorithms for optimization problems in fixed dimension. J. Algorithms 21(3), 579–597 (1996)

    Article  MathSciNet  Google Scholar 

  16. Clarkson, K.L., Shor, P.W.: Applications of random sampling in computational geometry. II. Discrete Comput. Geom. 4(5), 387–421 (1989)

    Article  MathSciNet  Google Scholar 

  17. Clarkson, K.L., Varadarajan, K.: Improved approximation algorithms for geometric set cover. Discrete Comput. Geom. 37(1), 43–58 (2007)

    Article  MathSciNet  Google Scholar 

  18. Dudley, R.M.: Notes on empirical processes. Lecture notes, Aarhus Universitet (2000)

  19. Dutta, K., Ghosh, A., Jartoux, B., Mustafa, N.H.: Shallow packings, semialgebraic set systems, Macbeath regions, and polynomial partitioning. Discrete Comput. Geom. 61(4), 756–777 (2019)

    Article  MathSciNet  Google Scholar 

  20. Even, G., Rawitz, D., Shahar, Sh.: Hitting sets when the VC-dimension is small. Inf. Process. Lett. 95(2), 358–362 (2005)

    Article  MathSciNet  Google Scholar 

  21. Grelier, N., Ilchi, S.Gh., Miltzow, T., Smorodinsky, Sh.: On the VC-dimension of half-spaces with respect to convex sets. Discrete Math. Theor. Comput. Sci. 23(3), # 2 (2021)

  22. Haussler, D., Welzl, E.: \(\varepsilon \)-nets and simplex range queries. Discrete Comput. Geom. 2(2), 127–151 (1987)

    Article  MathSciNet  Google Scholar 

  23. Kedem, K., Livné, R., Pach, J., Sharir, M.: On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles. Discrete Comput. Geom. 1(1), 59–71 (1986)

    Article  MathSciNet  Google Scholar 

  24. Keevash, P.: Hypergraph Turán problems. In: Surveys in Combinatorics 2011 (Exeter 2011). London Math. Soc. Lecture Note Ser., vol. 392, pp. 83–139. Cambridge University Press, Cambridge (2011)

  25. Keller, Ch., Smorodinsky, Sh.: Conflict-free coloring of intersection graphs of geometric objects. Discrete Comput. Geom. 64(3), 916–941 (2020)

    Article  MathSciNet  Google Scholar 

  26. Keszegh, B.: Coloring intersection hypergraphs of pseudo-disks. Discrete Comput. Geom. 64(3), 942–964 (2020)

    Article  MathSciNet  Google Scholar 

  27. Komlós, J., Pach, J., Woeginger, G.: Almost tight bounds for \(\varepsilon \)-nets. Discrete Comput. Geom. 7(2), 163–173 (1992)

    Article  MathSciNet  Google Scholar 

  28. Li, Y., Long, P.M., Srinivasan, A.: Improved bounds on the sample complexity of learning. J. Comput. System Sci. 62(3), 516–527 (2001)

    Article  MathSciNet  Google Scholar 

  29. Liu, C.L.: Introduction to Combinatorial Mathematics. McGraw-Hill, New York–Toronto–London (1968)

  30. Matoušek, J.: Approximations and optimal geometric divide-and-conquer. J. Comput. System Sci. 50(2), 203–208 (1995)

    Article  MathSciNet  Google Scholar 

  31. Matoušek, J.: Geometric Discrepancy. Algorithms and Combinatorics, vol. 18. Springer, Berlin (1999)

  32. Matoušek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol. 212. Springer, New York (2002)

  33. Matoušek, J., Welzl, E., Wernisch, L.: Discrepancy and \(\varepsilon \)-approximations for bounded VC-dimension. In: 32nd Annual Symposium on Foundations of Computer Science (San Juan 1991), pp. 424–430. IEEE, Los Alamitos (1991)

  34. Mustafa, N.H., Ray, S.: \(\varepsilon \)-Mnets: hitting geometric set systems with subsets. Discrete Comput. Geom. 57(3), 625–640 (2017)

    Article  MathSciNet  Google Scholar 

  35. Mustafa, N.H., Varadarajan, K.: Epsilon-approximations & epsilon-nets. In: Handbook of Discrete and Computational Geometry, 3rd ed., pp. 1241–1267. CRC Press, Boca Raton (2018)

  36. Pach, J., Tardos, G.: Tight lower bounds for the size of epsilon-nets. J. Am. Math. Soc. 26(3), 645–658 (2013)

    Article  MathSciNet  Google Scholar 

  37. Pyrga, E., Ray, S.: New existence proofs for \(\epsilon \)-nets. In: 24th Annual Symposium on Computational Geometry (College Park 2008), pp. 199–207. ACM, New York (2008)

  38. Rabani, Y., Shpilka, A.: Explicit construction of a small \(\epsilon \)-net for linear threshold functions. SIAM J. Comput. 39(8), 3501–3520 (2010)

    Article  MathSciNet  Google Scholar 

  39. Raman, R., Ray, S.: Constructing planar support for non-piercing regions. Discrete Comput. Geom. 64(3), 1098–1122 (2020)

    Article  MathSciNet  Google Scholar 

  40. Sauer, N.: On the density of families of sets. J. Combin. Theory Ser. A 13(1), 145–147 (1972)

    Article  MathSciNet  Google Scholar 

  41. Scott, A., Seymour, P.: A survey of \(\chi \)-boundedness. J. Graph Theory 95(3), 473–504 (2020)

    Article  MathSciNet  Google Scholar 

  42. Shamir, A.: How to share a secret. Commun. ACM 22(11), 612–613 (1979)

    Article  MathSciNet  Google Scholar 

  43. Shelah, S.: A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific J. Math. 41, 247–261 (1972)

    Article  MathSciNet  Google Scholar 

  44. Simmons, G.J.: How to (really) share a secret. In: Advances in Cryptology (Santa Barbara 1988). Lecture Notes in Comput. Sci., vol. 403, pp. 390–448. Springer, Berlin (1990)

  45. Talagrand, M.: Sharper bounds for Gaussian and empirical processes. Ann. Probab. 22(1), 28–76 (1994)

    Article  MathSciNet  Google Scholar 

  46. Tassa, T.: Hierarchical threshold secret sharing. J. Cryptol. 20(2), 237–264 (2007)

    Article  MathSciNet  Google Scholar 

  47. Vapnik, V.N., Chervonenkis, A.Ya.: On the uniform convergence of relative frequencies of events to their probabilities. Theor. Prob. Appl. 16(2), 264–280 (1971)

  48. Wagon, S.: A bound on the chromatic number of graphs without certain induced subgraphs. J. Combin. Theory Ser. B 29(3), 345–346 (1980)

    Article  MathSciNet  Google Scholar 

  49. Welzl, E.: Partition trees for triangle counting and other range searching problems. In: 4th Annual Symposium on Computational Geometry (Urbana 1988), pp. 23–33. ACM, New York (1988)

Download references

Acknowledgements

The authors are grateful to Adi Shamir for fruitful suggestions regarding the application of \(\varepsilon \)–t-nets to secret sharing.

Author information

Authors and Affiliations

  1. Department of Mathematics, Princeton University, Princeton, NJ, 08544, USA

    Noga Alon

  2. Schools of Mathematics and Computer Science, Tel Aviv University, Tel Aviv, 69978, Israel

    Noga Alon

  3. Department of Computer Science, Ben-Gurion University of the Negev, Be’er-Sheva, Israel

    Bruno Jartoux

  4. Department of Computer Science, Ariel University, Ariel, Israel

    Chaya Keller

  5. Department of Mathematics, Ben-Gurion University of the Negev, Be’er-Sheva, Israel

    Shakhar Smorodinsky & Yelena Yuditsky

Authors
  1. Noga Alon
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bruno Jartoux
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Chaya Keller
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Shakhar Smorodinsky
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Yelena Yuditsky
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Bruno Jartoux.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

Editor in Charge: János Pach

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

An abridged version of this paper appeared in the Proceedings of the 36th International Symposium on Computational Geometry (SoCG 2020). Noga Alon: Research supported in part by NSF Grant DMS-1855464, ISF Grant 281/17, GIF Grant G-1347-304.6/2016, and the Simons Foundation. Bruno Jartoux: Research supported by the European Research Council under the European Union’s Horizon 2020 research and innovation programme (Grant Agreement No. 678765) and by Grants 635/16 and 1065/20 from the Israel Science Foundation. Chaya Keller: Part of the research was done when the author was at the Technion, Israel. Supported by Grants 409/16 and 1065/20 from the Israel Science Foundation. Shakhar Smorodinsky: Research partially supported by Grants 635/16 and 1065/20 from the Israel Science Foundation. Yelena Yuditsky: Research supported by the European Research Council under the European Union’s Horizon 2020 research and innovation programme (Grant Agreement No. 678765) and by Grants 635/16 and 1065/20 from the Israel Science Foundation.

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Alon, N., Jartoux, B., Keller, C. et al. The \(\varepsilon \)-t-Net Problem. Discrete Comput Geom 68, 618–644 (2022). https://doi.org/10.1007/s00454-022-00376-x

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00454-022-00376-x

Keywords

Mathematics Subject Classification

Search

Navigation