Ph.D. Thesis

M.Sc. Thesis

Publications, by topic

Discrete Geometry

1. Gabriel Nivasch, János Pach, Rom Pinchasi, and Shira Zerbib,
   The number of distinct distances from a vertex of a convex polygon [arXiv:1207.1266]
   Journal of Computational Geometry, 4:1-12, 2013.

   

   Erdős conjectured in 1946 that every n-point set P in convex position in the plane contains a point that determines at least floor(n/2) distinct distances to the other points of P. The best known lower bound due to Dumitrescu (2006) is 13n/36 – O(1). In the present note, we slightly improve on this result to (13/36 + eps)n – O(1) for eps ≈ 1/23000. Our main ingredient is an improved bound on the maximum number of isosceles triangles determined by P.

2. Gabriel Nivasch, János Pach, and Gábor Tardos,
   The visible perimeter of an arrangement of disks [arXiv:1206.1422]
   Extended abstract in Graph Drawing 2012 (Lecture Notes in Computer Science, 7704:364-375, 2013).
   Full version submitted.

   

   Given a collection of n opaque unit disks in the plane, we want to find a stacking order for them that maximizes their total visible perimeter. The problem is hardest when the set of centers is uniformly shrunk until it is very small. We show that if the set of centers is dense and very small, then: (1) there is always a stacking order that achieves visible perimeter Ω(n^2/3); (2) every stacking order achieves visible perimeter O(n^3/4); and (3) both bounds are asymptotically tight.

3. Boris Bukh and Gabriel Nivasch,
   Upper bounds for centerlines [arXiv:1107.3421]
   Journal of Computational Geometry, 3:20-30, 2012.

   

   Bukh, Matousek, and Nivasch made the following conjecture: For every n-point set S in R^d and every k, there exists a k-flat f in R^d (a "centerflat") at "depth" at least (k+1) n / (k+d+1) with respect to S, in the sense that every halfspace that contains f contains at least that many points of S. For k=0 this is the centerpoint theorem, and for k = d–1 it is trivial. Bukh et al. proved the case k = d–2.
   In this paper we focus on the case k = 1 (the case of "centerlines"). We show that the "stretched grid" provides a tight upper bound for the conjecture; meaning, no line in R^d lies at depth larger than 2n / (d+2) with respect to the n-point stretched grid.
   

4. Boris Bukh, Jiri Matousek, and Gabriel Nivasch,
   Lower bounds for weak epsilon-nets and stair-convexity
   Extended abstract in Proc. 25th ACM Symp. on Computational Geometry (SoCG 2009), pp. 1–10, 2009 [PDF].
   Full version in Israel Journal of Mathematics, 182:199-228, 2011 [arXiv:0812.5039].

   

   For every fixed d ≥ 2 and every r ≥ 1 we construct point sets in R^d for which every weak 1/r-net has at least Ω(r log^d–1 r) points. This is the first superlinear lower bound for weak epsilon-nets in a fixed dimension. The construction is a "stretched grid", i.e., the Cartesian product of d suitable fast-growing finite sequences, and convexity in this grid can be analyzed using "stair-convexity", a new variant of the usual notion of convexity.

5. Gabriel Nivasch,
   Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations
   Extended abstract in Proc. 20th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 1–10, 2009. SODA 2009 Best Student Paper!
   Full version in Journal of the ACM, 57, article 17, 44 pages, 2010 [arXiv:0807.0484].

   

   Davenport-Schinzel sequences have strange upper and lower bounds of the form n⋅2^poly(α(n)), where α(n) denotes the inverse Ackermann function (Agarwal, Sharir, and Shor, 1989).
   In this paper we derive improved upper bounds for DS sequences of general order s. The bounds are now asymptotically tight for s even.
   More importantly, we also present a new upper-bound technique, based on recurrences very similar to those for "stabbing interval chains". With this new technique we re-derive our new upper bounds, and we also derive tighter upper bounds for generalized DS sequences.
   Regarding lower bounds, we present a construction for DS sequences of order 3 with optimal leading coefficient. We also present a simpler variant of the construction of Agarwal, Sharir and Shor for sequences of even order s≥4.

6. Boris Bukh, Jiri Matousek, and Gabriel Nivasch,
   Stabbing simplices by points and flats [arXiv:0804.4464]
   Discrete and Computational Geometry, 43:321–338, 2010.

   

   We construct an n-point set S in R^d such that no point in R^d stabs more than (n / (d+1))^d+1 + O(n^d) simplices spanned by S. We also prove that for every n-point set S in R^d there exists a (d–2)-flat that stabs at least (1 – (2d–1)^–2) n³ / 24 – O(n²) triangles spanned by S. This latter bound follows from the following equipartition result: Every mass distribution in R^d can be divided into 4d – 2 equal parts by 2d – 1 hyperplanes passing through a common (d–2)-flat.

7. Gabriel Nivasch and Micha Sharir,
   Eppstein's bound on intersecting triangles revisited [arXiv:0804.4415]
   Journal of Combinatorial Theory, Series A, 116:494–497, 2009.

   

   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 Ω(m³ / (n⁶ log² n)) triangles of T. Eppstein (1993) gave a proof of this claim, but there is a problem with his proof. Here we provide a correct proof by slightly modifying Eppstein's argument.

8. Noga Alon, Haim Kaplan, Gabriel Nivasch, Micha Sharir, and Shakhar Smorodinsky,
   Weak ε-nets and interval chains
   Extended abstract in Proc. 19th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 1194–1203, 2008 [PDF].
   Full version in Journal of the ACM, 55, article 28, 32 pages, 2008 [PDF].

   

   We construct weak epsilon-nets of almost linear size for some special types of point sets. Our bounds involve the extremely slow-growing inverse Ackermann function. The constructions result from a reduction to a new problem, which we call stabbing interval chains. We derive almost-tight upper and lower bounds for this new problem, involving functions of the inverse Ackermann hierarchy.

9. Gabriel Nivasch,
   An improved, simple construction of many halving edges [PDF]
   In Surveys on Discrete and Computational Geometry: Twenty Years Later (J. E. Goodman et al., editors), Contemporary Mathematics 453, pp. 299–305, AMS, 2008.

   

   We construct, for every even n, a set of n points in the plane that generates Ω(n e^{(√ ln 4) √ ln n} / √ ln n) halving edges. This improves Géza Tóth's previous bound by a constant factor in the exponent. Our construction is significantly simpler than Tóth's.

Combinatorial Game Theory

1. Gabriel Nivasch,
   The Sprague-Grundy function of the game Euclid [PDF]
   Discrete Mathematics, 306:2798–2800, 2006.

   

   The Sprage-Grundy function of the game Euclid is given by g(x, y) = floor[|y/x - x/y|].

2. Gabriel Nivasch,
   More on the Sprague-Grundy function for Wythoff's game
   In Games of No Chance 3 (M. H. Albert and R. J. Nowakowski, editors), MSRI Publications 56, pp. 377–410, Cambridge University Press, 2009.

   

   We prove that, for every fixed g, the g-values of Wythoff's Sprague-Grundy function lie roughly along two diagonals, of slopes φ and φ^-1, radiating from the origin. We also present a convergence conjecture which, if true, yields a recursive algorithm for finding the n-th g-value in O(log n) arithmetical operations.

Miscellaneous

1. Gabriel Nivasch and Eyal Lev,
   Non-attacking queens on a triangle [PDF]
   Mathematics Magazine, 78:399–403, 2005.

   

   How many non-attacking queens can be placed on a triangular board of side n?

2. Gabriel Nivasch,
   Cycle detection using a stack [PDF]
   Information Processing Letters, 90:135–140, 2004.

   A cute and efficient algorithm for detecting periodicity in sequences produced by repeated application of a given function.

Unpublished

1. Gabriel Nivasch,
   Experimental results on Hamiltonian-cycle-finding algorithms, 2003 [PDF]

   

   A project I did under the supervision of Prof. Uriel Feige, at the Weizmann Institute.
   We tested a certain heuristic Hamiltonian-cycle algorithm by searching for solutions to knight tour problems. We got some surprising behavior when we added fake edges to the graphs—edges that provably are not part of any Hamiltonian cycle. The algorithm performed better with fake edges!