56 citations · 167 across the 20 of their papers we have counts for
4 papers · 1 filter
Lower bounds for weak epsilon-nets and stair-convexity
Boris Bukh, Jiří Matoušek, Gabriel Nivasch
A set N is called a "weak epsilon-net" (with respect to convex sets) for a finite set X in R^d if N intersects every convex set that contains at least epsilon*|X| points of X. For…
Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations
Gabriel Nivasch
Let lambda_s(n) denote the maximum length of a Davenport-Schinzel sequence of order s on n symbols. For s=3 it is known that lambda_3(n) = Theta(n alpha(n)) (Hart and Sharir, 1986)…
Stabbing simplices by points and flats
Boris Bukh, Jiří Matoušek, Gabriel Nivasch
The following result was proved by Barany in 1982: For every d >= 1 there exists c_d > 0 such that for every n-point set S in R^d there is a point p in R^d contained in at least c_…
Eppstein's bound on intersecting triangles revisited
Gabriel Nivasch, Micha Sharir
Let S be a set of n points in the plane, and let T be a set of m triangles with vertices in S. Then there exists a point in the plane contained in Omega(m^3 / (n^6 log^2 n)) triang…