Publications
N. Rubin,An Improved Bound for Weak Epsilon-Nets in The Plane, Journal of the ACM 69 (5) 2022, Article 32. Extended abstract appeared in Proceedings of FOCS 2018. (Full version submitted to a journal.) Improving the 25 year old bound of Alon, Barany, Furedi and Kleitman.
N. Rubin, Stronger Bounds for Weak Epsilon-Nets in Higher Dimensions , Proceedings of STOC 2021. Improving the 1993 weak epsilon-net bound of Chazelle et al. in all dimensions
J. Pach, N. Rubin and G. Tardos, Planar Point Sets Determine Many Pairwise Crossing Segments, accepted to Advances in Mathematics, 2021. Also in Proceedings of STOC 2019. We show that any complete (or sufficiently dense) geometric graph determines n^{1-o(1)} pairwise crossing edges. This improves the 1990 bound of Aronov, Erdos, Goddard, Kleitman, Pach and Schulman.
L. Martinez, E. Roldan-Pensado, and N. Rubin, Further Consequences of The Colourful Helly Hypothesis Invited and accepted to a special issue of Discrete and Computational Geometry. Also in proceedings of Symposium on Computational Geometry, 2018
We establish further structural properties of families of convex sets that satisfy the conditions of Lovasz colourful Helly Theorem.
J. Pach, N. Rubin and G. Tardos, A Crossing Lemma for Jordan Curves, Advances in Mathematics 331 (2018), 908 -- 940.
We establish a proper analogue of the Crossing Lemma for contact graphs of Jordan curves. For any family with at least linearly
many touching pairs we show that the number of touchings grows asymptotically faster than the number of crossings.
P. K. Agarwal, N. Rubin and M. Sharir, Approximate Nearest Neighbor Search Amid Higher-Dimensional Flats,
Proc. 25th Annual European Symposium on Algorithms (ESA 2017)
J. Pach, N. Rubin and G. Tardos, Beyond The Richter-Thomassen Conjecture
Proc. 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016)
If two closed Jordan curves in the plane have precisely one point in common, then it is called a touching point. All other intersection points are called crossing points. The main result of this paper is a Crossing Lemma for closed curves: In any family of n pairwise intersecting simple closed curves in the plane, no three of which pass through the same point, the number of crossing points exceeds the number of touching points by a factor of at least Omega((\log\log n)^{1/8}).
As a corollary, we prove the following long-standing conjecture of Richter and Thomassen: The total number of intersection points between any $n$ pairwise intersecting simple closed curves in the plane, no three of which pass through the same point, is at least (1-o(1))n^2.
J. Pach, N. Rubin and G. Tardos, On The Richter-Thomassen Conjecture about Pairwise Intersecting Closed Curves
Combinatorics, Probability and Computing 25 (6) (2016), 941 - 958.
Extended abstract appeared in Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015)
It has long been conjectured that any family of n pairwise intersecting curves in the plane admits at least (2-o(1))n
pairwise-intersection points. The conjecture follows from the following stronger claim: the number of proper crossing points
is asymptotically larger than the number of touching pairs of curves (which intersect at a single touching point).
The SODA paper confirms the asymptotic claim for all families of monotone or convex curves.
N. Rubin,
On Kinetic Delaunay Triangulations: A Near Quadratic Bound for Unit Speed Motions,
Proc. 54th Annual Symposium on Foundations of Computer Science (FOCS 2013). Best paper award!
Full version invited to, and appeared in Journal of ACM 62 (3) (2015), Article 25.
The paper solves this open problem. For any finite set of points moving along lines at uniform speed,
we establish an almost-sharp near quadratic upper bound on the total number of discrete changes experienced
by their Delaunay triangulation.
Our analysis is far more general and is cast in a purely topological setting. The presentation is self-contained, with main ideas
delivered already in Sections 1-4.
P. K. Agarwal, H. Kaplan, N. Rubin and M. Sharir
Kinetic Voronoi Diagrams and Delaunay Triangulations under Polygonal Distance Functions,
Discrete and Computational Geometry 4 (4) (2015), 871 - 904.
P. K. Agarwal, J. Gao, L. J. Guibas, H. Kaplan, N. Rubin and M. Sharir, Stable Delaunay Graphs
Discrete and Computational Geometry 54 (4) (2015), 905 - 929..
We introduce an easy-to-maintain subgraph of the Euclidean Delaunay triangulation, which is
robust with respect to small changes of the underlying "unit ball" of the distance function.
N. Rubin, On topological changes in the Delaunay triangulation of moving points,
Proc. 28th Annu. Symp. Comput. Geom. (SoCG 2012), pp. 1--10. Best paper award!
Full version has appeared in Discrete & Computational Geometry 49(4) (2013), pp. 710--746.
This very accessible paper obtains a weaker topological variant of the FOCS 2013 result.
N. Rubin, H. Kaplan and M. Sharir Improved Bounds for Geometric Permutations,
SIAM Journal of Computing 41(2) (2012), pp. 367--390.
A preliminary version has appeared in Proc. 51st Annual IEEE Symposium on Foundations of Computer Science
(FOCS 2010), pp. 355--364.
We improve Wenger's 20-year old bound on the maximum number of geometric permutations that can be realized by line transversals
to n pairwise disjoint convex sets, in any dimension d larger than 2.
N. Rubin,
Discrete & Computational Geometry 48 (1) (2012), 65--93 (2012).
A preliminary version appeared in Proc. 26th Annu. Symp. on Computational Geometry (SoCG 2010), pp. 58--67.
We resolve a problem posed by Agarwal, Aronov, Koltun and Sharir, by extending their result to spheres of arbitrary radii in 3d.
P. K. Agarwal, J. Gao, L. Guibas, H. Kaplan, V.Koltun, N. Rubin and M. Sharir,
Proc. 26th Annu. Symp. on Computational Geometry (SoCG 2010), 127--136.
H. Kaplan, N. Rubin and M. Sharir,
A Kinetic Triangulation Scheme for Moving Points in The Plane,
Proc. 26th Annu. Symp. on Computational Geometry (SoCG 2010), 137--146.
Full version appeared in Computational Geometry: Theory & Applications 44(4) (2011), 191--205.
We introduce a relatively simple triangulation of a planar point set, which experiences only
near-quadratically many changes during any (fixed degree-)algebraic motion of the underlying point set.
H. Kaplan, N. Rubin and M. Sharir,
SIAM Journal of Computing 39 (2010), 3283--3310.
Also in Proc. 20th ACM-SIAM Symp. on Discrete Algorithms, (SODA 2009), 170--179.
We study the combinatorial complexity of the space of lines transversals to a family of k convex polyhedra with a total of n facets.
H. Kaplan, N. Rubin, M. Sharir and E. Verbin,
SIAM Journal of Computing 38 (2008), 982--1011.
A preliminary version appeared at SODA 2007.
We are to preprocess a set of colored points so as to report the number of distinct colors of points in
query hyperboxes. The complexity of this problem happens to be strongly related to that of matrix multiplication.
As a by-product, we establish several important results on the worst-case and expected number of maximal empty
hyperboxes induced by a set of points in d-space.
In addition, we provide an optimal decomposition of the union of orthants into pairwise disjoint hyperboxes.
H. Kaplan, N. Rubin and M. Sharir,
Linear data structures for fast ray shooting amidst convex polyhedra,
Algorithmica 55 (2009), 283--310.
A preliminary version appeared at ESA 2007.