One key to avoiding the inherent NP-hardness of these combinatorial problems is to take into account the geometric structure of data that exists in many applications. Such structures, however, become very large with data increases (which, e.g., for business data doubles worldwide every 1.2 years). This dismal state of affairs in theory then translates current applications still using heuristics with the hope (and no guarantees) that they would run fast and produce good-quality solutions. Recent effective approaches to large computational problems therefore rely on structures which are provably small; hence the field of streaming algorithms computes small `sketches' of data, or sub-linear algorithms that even avoid looking at the entire data using structures called epsilon-nets. The core of both these approaches is to show that the structural essence of the entire data can be captured by a small-sized subset. Closer to our theme, the key to the resolution of a long-standing open problem on minimum set-cover for disks was another small-sized structure, namely geometric separators.

The goal of this project is the design of provably efficient and reliable algorithms for packing and covering problems through the study of small-sized structural approximations of geometric data. This involves the analysis of geometric data (e.g., epsilon-nets) to construct small-sized geometric structures (e.g., separators) to design efficient algorithms for packing and covering problems for reliable software solution. A successful completion of this proposal would entail: new structural understanding of geometric data; leading directly to better algorithms for problems on geometric data; careful implementation and algorithmic fine-tuning; solving instances of specific problems of relevance to industry; and finally integration into the state-of-the-art libraries and technologies.

- Bruno Jartoux.
- Started on October 2015, graduated in October 2018.
- Thesis page.

Associated:

- Norbert Bus.
- Started on October 2012, graduated in October 2015.
- Thesis page.

- Monika Csikos.
- Started on October 2018.

- Janos Pach, EPFL, Lausanne, Switzerland.
- Arijit Ghosh, IISc., Calcutta, India.
- Kunal Dutta, INRIA, Nice, France.
- Imre Barany, UCL, London, UK.
- Marton Naszodi, ETU, Budapest, Hungary.
- Saurabh Ray, NYU, UAE.
- Monika Csikos, KIT, Karlsruhe, Germany.
- Daniel Antunes, Chambery, France.
- Andrey Kupavskii, Moscow, Russia.
- Victor Chepoi, Marseille, France.
- Alfonso Cevallos, ETH, Zurich, Switzerland.
- Jesus D. Loera, UC Davis, California, US.
- Norbert Bus, Telecom ParisTech, Paris, France.
- Justin Ward, QM University, London, UK.
- Guilherme Dias da Fonseca, Universite Clermont Auvergne, France.
- Dömötör Pálvölgyi, Eötvös Loránd University, Hungary.
- Csaba Toth, California State University Northridge, US.
- Konrad Swanepoel, LSE, UK.

- Approximation Algorithms and Geometric Convexity, 2018.
- Approximation Algorithms: Combinatorics, Geometry and Statistics, 2019.

- ENET: a near-linear time algorithm for epsilon-nets for disks in the plane.
- DNET: algorithms for computing hitting-sets for disks in the plane.

- Tverberg Theorems over Discrete Sets of Points.
(Jesús A. De Loera, Thomas Hogan, Frédéric Meunier, Nabil H. Mustafa).

*Submitted*, 2019.

- Optimality of Geometric Local Search.
(Bruno Jartoux, Nabil H. Mustafa).

*Submitted*, 2018.

- An Application of the Universality Theorem for Tverberg Partitions.
(Imre Barany, Nabil H. Mustafa).

*Submitted*, 2019.

- Maximizing Covered Area in a Euclidean Plane with Connectivity Constraint.
(Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Nabil H. Mustafa).

*Submitted*, 2019.

## 2019

- Computing Optimal Epsilon-nets is as Easy as Finding an Unhit Set.
(Nabil H. Mustafa).

*Proc. of the 46th International Colloquium on Automata, Languages and Programming (ICALP '19)*, 2019.

- Shallow Packings, Semialgebraic Set Systems, Macbeath Regions, and Polynomial Partitioning.
(Kunal Dutta, Arijit Ghosh, Bruno Jartoux, Nabil H. Mustafa).

*Discrete and Computational Geometry*, 2019. (link)

- Optimal Bounds for VC-dimensions of Unions.
(Monika Csikos, Andrey Kupavskii, Nabil H. Mustafa).

*Journal of Machine Learning Research (JMLR)*, 2019.

- The Discrete Yet Ubiquitous Theorems of Caratheodory, Helly, Sperner, Tucker and Tverberg.
(Jesus de Loera, Xavier Goaoc, Frederic Meunier, Nabil H. Mustafa).

*Bulletin of the American Mathematical Society*, 2019. DOI: https://doi.org/10.1090/bull/1653.

- Bounding the size of an almost-equidistant set in Euclidean space.
(Andrey Kupavskii, Nabil H. Mustafa, Konrad J. Swanepoel).

*Combinatorics, Probability and Computing*, doi: 10.1017/S0963548318000287, 2019.

- Theorems of Caratheodory, Helly and Tverberg without dimension.
(Karim Adiprasito, Imre Barany, Nabil H. Mustafa).

*Proc. of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA '19)*, 2019.

- On a Problem of Danzer.
(Nabil H. Mustafa, Saurabh Ray).

*Combinatorics, Probability and Computing*, doi: 10.1017/S0963548318000445, 2019.

## 2018

- A simple proof of optimal epsilon-nets.
(Nabil H. Mustafa, Kunal Dutta, Arijit Ghosh).

*Combinatorica*, doi:10.1007/s00493-017-3564-5, 2017.

- On a Problem of Danzer.
(Nabil H. Mustafa, Saurabh Ray).

*Proc. of the 26th Annual Symposium on Algorithms (ESA '18)*, 2018.

- Optimality of Geometric Local Search.
(Bruno Jartoux, Nabil H. Mustafa).

*Proc. of the 34th ACM Symposium on Computational Geometry (SoCG '18)*, 2018.

- Integer and Mixed Integer Tverberg Numbers.
(Jesús A. De Loera, Thomas Hogan, Frédéric Meunier, Nabil H. Mustafa).

*34th European Workshop on Computational Geometry (EuroCG)*, 2018.

- Practical and Efficient Algorithms for the Geometric Hitting Set Problem.
(Norbert Bus, Nabil H. Mustafa, Saurabh Ray).

*Discrete Applied Mathematics*, vol 240, pp. 25-32, 2018.

## 2017

- Combinatorics of Local Search: A 4-Local Hall's Theorem for Planar Graphs.
(Daniel Antunes, Claire Mathieu, Nabil H. Mustafa).

*Proc. of the 25th Annual Symposium on Algorithms (ESA '17)*, 2017.

- Epsilon-Mnets: Hitting geometric set systems with subsets.
(Nabil H. Mustafa, Saurabh Ray).

*Discrete and Computational Geometry*, vol 57, pp. 625-640, 2017.

- Limits of Local Search: Quality and Efficiency.
(Norbert Bus, Shashwat Garg, Nabil H. Mustafa, Saurabh Ray).

*Discrete and Computational Geometry*, vol 57, pp. 607-624, 2017.

- Shallow Packings, Semialgebraic Set Systems, Macbeath Regions and Polynomial Partitioning.
(Kunal Dutta, Arijit Ghosh, Bruno Jartoux, Nabil H. Mustafa).

*Proc. of the 33rd ACM Symposium on Computational Geometry (SoCG '17)*, 2017.

- Near-optimal lower bounds for epsilon-nets for half-spaces and low complexity set systems.
(Andrey Kupavskii, Nabil H. Mustafa, Janos Pach).

Book chapter in*A Journey Through Discrete Mathematics: A Tribute to Jirí Matousek*, Springer, 2017. Book link.

- Epsilon-approximations and epsilon-nets.
(Nabil H. Mustafa, Kasturi Varadarajan).

Book chapter in*Handbook of Discrete and Computational Geometry, Third Edition*, CRC Press, 2017. arXiv version.

## 2016

- A Simple Proof of the Shallow Packing Lemma.
(Nabil H. Mustafa).

*Discrete and Computational Geometry*, vol. 55(3), pp. 739-743, 2016.

- On the Zarankiewicz Problem for Intersection Hypergraphs.
(Nabil H. Mustafa, Janos Pach).

*Journal of Combinatorial Theory Series A*, vol 141, pp. 1-7, 2016.

- Tighter Estimates for Epsilon-nets for Disks.
(Norbert Bus, Saurabh Ray).

*Computational Geometry: Theory and Applications*, vol. 53, pp. 27-35, 2016.

- An Optimal Generalization of the Colorful Caratheodory's Theorem.
(Nabil H. Mustafa, Saurabh Ray).

*Discrete Mathematics*, 339(4), pp. 1300-1305, 2016.

- New Lower Bounds for Epsilon-nets.
(Andrey Kupavskii, Nabil H. Mustafa, Janos Pach).

*Proc. of the 32nd ACM Symposium on Computational Geometry (SoCG '16)*, 2016.

## 2015

- QPTAS for Weighted Geometric Set Cover on Pseudodisks and Halfspaces.
(Nabil H. Mustafa, Rajiv Raman, Saurabh Ray).

*SIAM Journal on Computing*, 44(6), pp. 1650-1669, 2015.

- K-Centerpoints Conjectures for Pointsets in R^d.
(Nabil H. Mustafa, Saurabh Ray, Mudassir Shabbir).

*International Journal of Computational Geometry and Applications*, vol. 25(3), pp. 163-185, 2015.

- On the Zarankiewicz Problem for Intersection Hypergraphs.
(Nabil H. Mustafa, Janos Pach).

*Proc. of the 23rd International Symposium on Graph Drawing and Network Visualization (GD '15)*, 2015.

- Geometric Hitting Sets for Disks: Theory and Practice.
(Norbert Bus, Nabil H. Mustafa, Saurabh Ray).

*Proc. of the 23rd European Symposium on Algorithms (ESA '15)*, 2015.

- Improved Local-Search for Geometric Hitting Set.
(Norbert Bus, Shashwat Garg, Nabil H. Mustafa, Saurabh Ray).

*Proc. of the 32st International Symposium on Theoretical Aspects of Computer Science (STACS '15)*, 2015.

All related publications need to mention the support from the project as follows: