5 citations · 14 across the 7 of their papers we have counts for
12 papers
A Greedy Algorithm for Low-Crossing Partitions for General Set Systems
Mónika Csikós, Alexandre Louvet, Nabil Mustafa
Simplicial partitions are a fundamental structure in computational geometry, as they form the basis of optimal data structures for range searching and several related problems. Cur…
Algorithms for Discrepancy, Matchings, and Approximations: Fast, Simple, and Practical
Mónika Csikós, Nabil H. Mustafa
We study one of the key tools in data approximation and optimization: low-discrepancy colorings. Formally, given a finite set system , the \emph{discrepancy} of a t…
Optimal Approximations Made Easy
Mónika Csikós, Nabil H. Mustafa
The fundamental result of Li, Long, and Srinivasan on approximations of set systems has become a key tool across several communities such as learning theory, algorithms, computatio…
Optimal Bounds on the VC-dimension
Monika Csikos, Andrey Kupavskii, Nabil H. Mustafa
The VC-dimension of a set system is a way to capture its complexity and has been a key parameter studied extensively in machine learning and geometry communities. In this paper, we…
Theorems of Carathéodory, Helly, and Tverberg without dimension
Karim Adiprasito, Imre Bárány, Nabil H. Mustafa +1
We prove a no-dimensional version of Carathédory's theorem: given an -element set , a point $a \in \conv P$, and an integer , , there is a subse…
Tverberg theorems over discrete sets of points
Jesús A. De Loera, Thomas A. Hogan, Frédéric Meunier +1
This paper discusses Tverberg-type theorems with coordinate constraints (i.e., versions of these theorems where all points lie within a subset and the inte…
Bounding the size of an almost-equidistant set in Euclidean space
Andrey Kupavskii, Nabil H. Mustafa, Konrad J. Swanepoel
A set of points in d-dimensional Euclidean space is almost equidistant if among any three points of the set, some two are at distance 1. We show that an almost-equidistant set in $…
The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
Jesus A. De Loera, Xavier Goaoc, Frédéric Meunier +1
We discuss five discrete results: the lemmas of Sperner and Tucker from combinatorial topology and the theorems of Carathéodory, Helly, and Tverberg from combinatorial geometry. We…
Epsilon-approximations and epsilon-nets
Nabil H. Mustafa, Kasturi R. Varadarajan
The use of random samples to approximate properties of geometric configurations has been an influential idea for both combinatorial and algorithmic purposes. This chapter considers…
A Note on the Size-Sensitive Packing Lemma
Nabil H. Mustafa
We show that the size-sensitive packing lemma follows from a simple modification of the standard proof, due to Haussler and simplified by Chazelle, of the packing lemma.
Tighter Estimates for epsilon-nets for Disks
Norbert Bus, Shashwat Garg, Nabil H. Mustafa +1
The geometric hitting set problem is one of the basic geometric combinatorial optimization problems: given a set of points, and a set of geometric objects in the…
QPTAS for Geometric Set-Cover Problems via Optimal Separators
Nabil H. Mustafa, Rajiv Raman, Saurabh Ray
Weighted geometric set-cover problems arise naturally in several geometric and non-geometric settings (e.g. the breakthrough of Bansal-Pruhs (FOCS 2010) reduces a wide class of mac…