Natan Rubin

According to our database, Natan Rubin authored at least 24 papers between 2007 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of two.

2024

An Efficient Regularity Lemma for Semi-Algebraic Hypergraphs.

Natan Rubin

CoRR, 2024

Improved Bounds for Point Selections and Halving Hyperplanes in Higher Dimensions.

Natan Rubin

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2022

An Improved Bound for Weak Epsilon-nets in the Plane.

Natan Rubin

J. ACM, 2022

2021

Stronger bounds for weak epsilon-nets in higher dimensions.

Natan Rubin

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

2020

Further Consequences of the Colorful Helly Hypothesis.

Leonardo Martínez-Sandoval, Edgardo Roldán-Pensado, Natan Rubin

Discret. Comput. Geom., 2020

2019

Planar point sets determine many pairwise crossing segments.

János Pach, Natan Rubin, Gábor Tardos

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

2017

A Crossing Lemma for Jordan Curves.

János Pach, Natan Rubin, Gábor Tardos

CoRR, 2017

Approximate Nearest Neighbor Search Amid Higher-Dimensional Flats.

Pankaj K. Agarwal, Natan Rubin, Micha Sharir

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

2016

On the Richter-Thomassen Conjecture about Pairwise Intersecting Closed Curves.

János Pach, Natan Rubin, Gábor Tardos

Comb. Probab. Comput., 2016

Beyond the Richter-Thomassen Conjecture.

János Pach, Natan Rubin, Gábor Tardos

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2015

On Kinetic Delaunay Triangulations: A Near-Quadratic Bound for Unit Speed Motions.

Natan Rubin

J. ACM, 2015

Kinetic Voronoi Diagrams and Delaunay Triangulations under Polygonal Distance Functions.

Pankaj K. Agarwal, Haim Kaplan, Natan Rubin, Micha Sharir

Discret. Comput. Geom., 2015

Stable Delaunay Graphs.

Pankaj K. Agarwal, Jie Gao, Leonidas J. Guibas, Haim Kaplan, Natan Rubin, Micha Sharir

Discret. Comput. Geom., 2015

2013

On Topological Changes in the Delaunay Triangulation of Moving Points.

Natan Rubin

Discret. Comput. Geom., 2013

2012

Improved Bounds for Geometric Permutations.

Natan Rubin, Haim Kaplan, Micha Sharir

SIAM J. Comput., 2012

Lines Avoiding Balls in Three Dimensions Revisited.

Natan Rubin

Discret. Comput. Geom., 2012

2011

Lines in higher dimensions

Natan Rubin

PhD thesis, 2011

A kinetic triangulation scheme for moving points in the plane.

Haim Kaplan, Natan Rubin, Micha Sharir

Comput. Geom., 2011

2010

Line Transversals of Convex Polyhedra in R³.

Haim Kaplan, Natan Rubin, Micha Sharir

SIAM J. Comput., 2010

Kinetic stable Delaunay graphs.

Pankaj K. Agarwal, Jie Gao, Leonidas J. Guibas, Haim Kaplan, Vladlen Koltun, Natan Rubin, Micha Sharir

Proceedings of the 26th ACM Symposium on Computational Geometry, 2010

2009

Linear Data Structures for Fast Ray-Shooting amidst Convex Polyhedra.

Haim Kaplan, Natan Rubin, Micha Sharir

Algorithmica, 2009

Line transversals of convex polyhedra in <i>R</i>³.

Haim Kaplan, Natan Rubin, Micha Sharir

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

2008

Efficient Colored Orthogonal Range Counting.

Haim Kaplan, Natan Rubin, Micha Sharir, Elad Verbin

SIAM J. Comput., 2008

2007

Counting colors in boxes.

Haim Kaplan, Natan Rubin, Micha Sharir, Elad Verbin

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007