Academic‎ > ‎

Publications

Ph.D. Thesis

Weak epsilon-nets, Davenport-Schinzel sequences, and related problems [PDF]
Tel Aviv University. Advisor: Micha Sharir. 2009

M.Sc. Thesis

The Sprague-Grundy function for Wythoff's game: On the location of the g-values [PDF]
Weizmann Institute of Science. Advisor: Aviezri S. Fraenkel. 2004

Publications

  1. David Eppstein, Sariel Har-Peled, and Gabriel Nivasch
    Grid peeling and the affine curve-shortening flow [arXiv:1710.03960]
    To appear in ALENEX 2018.

    [Picture]

    We observe that, experimentally, grid peeling (the convex-layer decomposition of subsets of the integer grid) seems to to behave at the limit like the affine curve-shortening flow. We offer some theoretical arguments to explain this phenomenon. We also derive some rigorous results for the special case of peeling the quarter-infinite grid.

  2. Boris Bukh, Po-Shen Loh, and Gabriel Nivasch,
    Classifying unavoidable Tverberg partitions [arXiv:1611.01078]
    Journal of Computational Geometry, 8(1):174-205, 2017.

    [Picture]

    We try to determine which types of Tverberg partitions unavoidably occur in every sufficiently long point sequence. We provide partial answers in dimensions up to 4.

  3. Boris Bukh and Gabriel Nivasch,
    One-sided epsilon-approximants [arXiv:1603.05717]
    A Journey through Discrete Mathematics: A Tribute to Jiří Matoušek (M. Loebl et al., editors), pp. 343-356, Springer, 2017.

    Given a finite point set P in Rd, we call a multiset A a one-sided weak ε-approximant for P (with respect to convex sets) if, for every convex set C in Rd, if α is the fraction of points of P contained in C, then C contains at least an (αε)-fraction of the points of A.
    We show that, in contrast with the usual (two-sided) weak ε-approximants, for every set P in Rd there exists a one-sided weak ε-approximant of size bounded by a function of ε and d.

  4. Gabriel Nivasch and Eran Omri,
    Rainbow matchings and algebras of sets [arXiv:1503.03671]
    Extended abstract in EuroComb 2015 (Electronic Notes in Discrete Mathematics, 49:251-257, 2015).
    Full version in Graphs and Combinatorics, 33:473-484, 2017.

    [Picture]

    What is the smallest number v = v(n) such that, if A1, ..., An are n equivalence relations on a common finite ground set X, such that for each i there are at least v elements of X that belong to Ai-equivalence classes of size larger than 1, then X contains a rainbow matching?
    Grinblat recently showed that v(n) ≤ 10n/3 + O(√n). We improve the bound to v(n) ≤ 16n/5 + O(1).

  5. Gabriel Nivasch
    On the zone of a circle in an arrangement of lines [arXiv:1503.03462]
    Extended abstract in EuroComb 2015 (Electronic Notes in Discrete Mathematics, 49:221-231, 2015).
    Full version in Discrete Mathematics, 340:1535-1552, 2017.

    [Picture]

    Edelsbrunner et al. (1992) showed that the zone of a convex curve (like a circle or a parabola) in an arrangement of lines has complexity O(n α(n)), where α is the inverse Ackermann function, by translating the sequence of edges of the zone into an ababa-free sequence S. Whether the complexity is only linear in n is a longstanding open problem.
    Here we provide evidence that, for the case of a circle/parabola, the zone complexity is at most linear: We show that a certain configuration of segments is geometrically impossible. As a consequence, the Hart-Sharir sequences, which are essentially the only known way to construct ababa-free sequences of superlinear length, cannot occur in S.

  6. Sathish Govindarajan and Gabriel Nivasch,
    A variant of the Hadwiger-Debrunner (p,q)-problem in the plane [arXiv:1409.1194]
    Discrete and Computational Geometry, 54:637-646, 2015.

    [Picture]

    Let X be a convex curve in the plane (say, the unit circle), and let S be a family of planar convex bodies, such that every two of them meet at a point of X. Then S has a transversal of size at most 1.75*109.
    Suppose instead that S only satisfies the following "(p,2)-condition": Among every p elements of S there are two that meet at a common point of X. Then S has a transversal of size O(p8). For comparison, the best known bound for the Hadwiger--Debrunner (p,q)-problem in the plane, with q=3, is O(p6).

  7. 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 in Computational Geometry: Theory and Applications, 47:42-51, 2014.

    [Picture] [picture]

    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 Ω(n2/3); (2) every stacking order achieves visible perimeter O(n3/4); and (3) both bounds are asymptotically tight.

  8. 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.

    [Picture]

    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.

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

    [Picture]

    Bukh, Matousek, and Nivasch made the following conjecture: For every n-point set S in Rd and every k, there exists a k-flat f in Rd (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 Rd lies at depth larger than 2n / (d+2) with respect to the n-point stretched grid.

  10. 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].

    [picture] [picture]

    For every fixed d ≥ 2 and every r ≥ 1 we construct point sets in Rd for which every weak 1/r-net has at least Ω(r logd–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.

  11. 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].

    [picture]

    Davenport-Schinzel sequences have strange upper and lower bounds of the form n⋅2poly(α(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.

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

    [picture] [picture]

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

  13. 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.

    [picture]

    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 Ω(m3 / (n6 log2 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.

  14. 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.

    [picture] [picture]

    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.

  15. 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].

    [picture] [picture]

    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.

  16. 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.

    [picture]

    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.

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

    [picture]

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

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

    [picture]

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

  19. 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]

    [picture]

    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!