Noga Alon, Haim Kaplan, Gabriel Nivasch, Shakhar Smorodinsky
Abstract. We construct weak ɛ-nets of almost linear size for certain types of point sets. Specifically, for planar point sets in convex position we construct weak 1-nets of size O(rα(r)), where...
Stabbing simplices by points and flats (2009)
The following result was proved by Bárány in 1982: For every d ≥ 1 there exists cd> 0 such that for every n-point set S in Rd there is a point p ∈ Rd contained in at least cdnd+1 − O(nd)...
Lower bounds for weak epsilon-nets and stair-convexity (2008)
Bukh, Boris, Matoušek, Jiří, Nivasch, Gabriel
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 every fixed d>=2...
Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations (2008)
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). For general s>=4...
Eppstein's bound on intersecting triangles revisited (2008)
Nivasch, Gabriel, Sharir, Micha
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)) triangles of T. Eppstein...
Stabbing simplices by points and flats (2008)
Bukh, Boris, Matoušek, Jiří, Nivasch, Gabriel
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_d n^{d+1} - O(n^d)...
Contemporary Mathematics An Improved, Simple Construction of Many Halving Edges (2008)
Abstract. We construct, for every even n, a set of n points in the plane that generates Ω ne √ ln 4 · √ ln n / √ ln n halving edges. This improves Tóth’s previous bound by a constant...
Weak ɛ-nets and interval chains (2007)
Noga Alon, Haim Kaplan, Gabriel Nivasch, Micha Sharir, Shakhar Smorodinsky
We construct weak ɛ-nets of almost linear size for certain types of point sets. Specifically, for planar point sets in convex position we construct weak 1 r-nets of size O(rα(r)), where α(r)...
Weak ɛ-nets and interval chains (2007)
Noga Alon, Haim Kaplan, Gabriel Nivasch, Micha Sharir, Shakhar Smorodinsky
We construct weak ɛ-nets of almost linear size for certain types of point sets. Specifically, for planar point sets in convex position we construct weak 1 r-nets of size O(rα(r)), where α(r)...
Non-attacking queens on a triangle (2005)
Most readers are surely familiar with the problem of placing eight non-attacking queens on a chessboard, and its natural generalization to an n × n board (see the references at the end of this...
Cycle detection using a stack (2004)
We present an algorithm for detecting periodicity in sequences produced by repeated application of a given function. Our algorithm uses logarithmic memory with high probability, runs in linear time,...
The Sprague-Grundy Function of the Game Euclid.” Manuscript and personal communication (2004)
We show that the Sprague-Grundy function of the game Euclid is given by g(x, y) = ⌊|y/x − x/y| ⌋ for x, y ≥ 1. Keywords: Combinatorial game; Impartial game; Euclid; Sprague-Grundy function.
Experimental Results on Hamiltonian-Cycle-Finding Algorithms (2003)
Frieze [1] introduced a heuristic polynomial-time algorithm, Ham, for finding Hamiltonian cycles in random graphs with high probability. We wanted to see