53 citations · 92 across the 32 of their papers we have counts for
41 papers
New Quantitative Bounds for the -Theorem for Unions of Convex Sets
Chaya Keller, Shakhar Smorodinsky
A set in is -convex if it is the union of at most convex sets. A family satisfies the property if among any sets in , some intersect. L…
A Colorful Extension of VC-dimension and Geometric Applications
Chaya Keller, Shakhar Smorodinsky
The VC-dimension is a fundamental measure of the complexity of a set system. In this paper, we introduce and study a colorful variant of VC-dimension that captures the behavior of…
New Sufficient Conditions for Linear-Sized Epsilon-Nets and -Theorems
Chaya Keller, Shakhar Smorodinsky
An -net theorem for a hypergraph upper bounds the minimum size of a vertex set that pierces all -heavy hyperedges. A -theorem bounds from above the minimum size of a v…
Extended VC-dimension, and Radon and Tverberg type theorems for unions of convex sets
Noga Alon, Shakhar Smorodinsky
We prove a new Radon type theorem for unions of convex sets, settling an open problem posed by Kalai in the 1970s. We also define and study an extension of the notion of the VC-dim…
Sparse Bounded Hop-Spanners for Geometric Intersection Graphs
Sujoy Bhore, Timothy M. Chan, Zhengcheng Huang +2
We present new results on - and -hop spanners for geometric intersection graphs. These include improved upper and lower bounds for - and -hop spanners for many geometri…
Polychromatic Coloring of Tuples in Hypergraphs
Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari +3
A hypergraph consists of a set of vertices and a set of hyperedges that are subsets of . A -tuple of is a subset of vertices of . A -tuple -color…