56 citations · 167 across the 20 of their papers we have counts for
11 papers · 1 filter
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" …
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…
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…
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…
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…