Algorithms for Multi-Dimensional Data via Sketches.
Massive geometric data is increasingly common thanks to the proliferation of ubiquitous data-collecting devices, presenting vexing challenges for algorithmic processing. Our approach to deal with this amount of data is to, given an approximation parameter eps, construct a small-sized sketch S of the input data, then solve the problem on S, and finally extend this solution to a (1+eps)-approximation to the original problem. Our research is divided into three parts, requiring expertise in statistics, computational geometry, learning, combinatorics, and algorithms. First, we consider the combinatorial properties of geometric data that are relevant to build compact sketches. Second, we consider the time and space complexities of constructing accurate sketches of data in high dimensions, based on the combinatorial and geometric understanding. Finally, we show how to use the small sketches in order to improve the accuracy and running time of optimization algorithms.
Team
Nabil H. Mustafa (project coordinator; Marne-la-vallée site coordinator)
poLYG: Polygon area minimization and maximization.
Publications (HAL pour les publications sous ADDS)
All related publications need to mention the support from the project as follows: Supported by the French ANR PRC grant ADDS (ANR-19-CE48-0005).
Books
Sampling in Combinatorial and Geometric Set Systems.
(Nabil Mustafa). American Mathematical Society (AMS), 2022. AMS link, Book website.
2025
A Greedy Algorithm for Low-Crossing Partitions for General Set Systems.
(Monika Csikos, Alexandre Louvet, Nabil Mustafa). SIAM Symposium on Algorithm Engineering and Experiments (ALENEX 2025), 2025.
2024
An Optimal Sparsification Lemma for Low-Crossing Matchings and its Applications to Discrepancy and Approximations.
(Monika Csikos, Nabil Mustafa). International Colloquium on Automata, Languages and Programming (ICALP 2024), 2024.
Complexity Results on Untangling Red-Blue Matchings
(Arun Kumar Das, Sandip Das, Guilherme D. da Fonseca, Yan Gerard, Bastien Rivier).
EuroCG 2022 special issue of Computational Geometry: Theory and Applications, 2023.
Complexity Results on Untangling Red-Blue Matchings.
(Arun Das, Sandip Das, Guilherme D. da Fonseca, Yan Gerard, Bastien Rivier). Proc. of the 15th Latin American Theoretical Informatics Symposium (LATIN), 2022.
Shadoks Approach to Low-Makespan Coordinated Motion Planning.
(Loďc Crombez, Guilherme D. da Fonseca, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, Luc Libralesso). Proc. of the 37th ACM Symposium on Computational Geometry (SoCG '21), 2021.
Tverberg Theorems over Discrete Sets of Points.
(Jesús A. De Loera, Thomas Hogan, Frédéric Meunier, Nabil H. Mustafa). Book chapter in Contemporary Mathematics: Polytopes and Discrete Geometry, AMS, 2021.