56 citations · 167 across the 20 of their papers we have counts for
23 papers
On the complexity of the free space of a translating box in R^3
Gabriel Nivasch
Consider a convex polyhedral robot that can translate (without rotating) amidst a finite set of non-moving polyhedral obstacles in . The "free space" …
A convergence technique for the game i-Mark
Gabriel Nivasch, Oz Rubinstein
The game of i-Mark is an impartial combinatorial game introduced by Sopena (2016). The game is parametrized by two sets of positive integers , , where . From pos…
Ordinals and recursively defined functions on the reals
Gabriel Nivasch, Lior Shiboli
We determine sufficient conditions under which certain recursively defined functions are well defined for all real inputs. Given a function , call a decrea…
Generalized fusible numbers and their ordinals
Alexander I. Bufetov, Gabriel Nivasch, Fedor Pakhomov
Erickson defined the fusible numbers as a set of reals generated by repeated application of the function . Erickson, Nivasch, and Xu showed that $\mat…
Some i-Mark games
Oren Friman, Gabriel Nivasch
Let be a set of positive integers, and let be a set of integers larger than . The game -Mark is an impartial combinatorial game introduced by Sopena (2016), wh…
Fusible numbers and Peano Arithmetic
Jeff Erickson, Gabriel Nivasch, Junyan Xu
Inspired by a mathematical riddle involving fuses, we define the "fusible numbers" as follows: is fusible, and whenever are fusible with , the number …
Nested Barycentric Coordinate System as an Explicit Feature Map
Lee-Ad Gottlieb, Eran Kaufman, Aryeh Kontorovich +2
We propose a new embedding method which is particularly well-suited for settings where the sample size greatly exceeds the ambient dimension. Our technique consists of partitioning…
Upper bounds for stabbing simplices by a line
Inbar Daum-Sadon, Gabriel Nivasch
It is known that for every dimension and every there exists a constant such that for every -point set there exists a -flat t…
Homotopic curve shortening and the affine curve-shortening flow
Sergey Avvakumov, Gabriel Nivasch
We define and study a discrete process that generalizes the convex-layer decomposition of a planar point set. Our process, which we call "homotopic curve shortening" (HCS), starts…
Learning convex polyhedra with margin
Lee-Ad Gottlieb, Eran Kaufman, Aryeh Kontorovich +1
We present an improved algorithm for {\em quasi-properly} learning convex polyhedra in the realizable PAC setting from data with a margin. Our learning algorithm constructs a consi…
Grid peeling and the affine curve-shortening flow
David Eppstein, Sariel Har-Peled, Gabriel Nivasch
In this paper we study an experimentally-observed connection between two seemingly unrelated processes, one from computational geometry and the other from differential geometry. Th…
Classifying unavoidable Tverberg partitions
Boris Bukh, Po-Shen Loh, Gabriel Nivasch
Let be the parameter in Tverberg's theorem, and call a partition of into parts a "Tverberg type". We say that $\mat…
One-sided epsilon-approximants
Boris Bukh, Gabriel Nivasch
Given a finite point set , we call a multiset a one-sided weak -approximant for (with respect to convex sets), if $|P\cap C|/|P|-|A\cap C…
Rainbow matchings and algebras of sets
Gabriel Nivasch, Eran Omri
Grinblat (2002) asks the following question in the context of algebras of sets: What is the smallest number such that, if are …
On the zone of a circle in an arrangement of lines
Gabriel Nivasch
Let be a set of lines in the plane, and let be a convex curve in the plane, like a circle or a parabola. The "zone" of in , denoted $\mathcal Z…
A variant of the Hadwiger-Debrunner (p,q)-problem in the plane
Sathish Govindarajan, Gabriel Nivasch
Let be a convex curve in the plane (say, the unit circle), and let be a family of planar convex bodies, such that every two of them meet at a point of . Then $\…
The number of distinct distances from a vertex of a convex polygon
Gabriel Nivasch, János Pach, Rom Pinchasi +1
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 visible perimeter of an arrangement of disks
Gabriel Nivasch, János Pach, Gábor Tardos
Given a collection of n opaque unit disks in the plane, we want to find a stacking order for them that maximizes their visible perimeter---the total length of all pieces of their b…
Upper bounds for centerlines
Boris Bukh, Gabriel Nivasch
In 2008, Bukh, Matousek, and Nivasch conjectured that for every n-point set S in R^d and every k, 0 <= k <= d-1, there exists a k-flat f in R^d (a "centerflat") that lies at "depth…
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…