Natan Rubin

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

Collaborative distances:

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

2025

An Efficient Regularity Lemma for Semi-Algebraic Hypergraphs.

Natan Rubin

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

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

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

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

2018

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

Natan Rubin

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Further Consequences of the Colorful Helly Hypothesis.

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

Proceedings of the 34th International Symposium on Computational Geometry, 2018

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

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

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

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

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

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2013

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

Natan Rubin

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

On topological changes in the delaunay triangulation of moving points.

Natan Rubin

Proceedings of the 28th ACM Symposium on Computational Geometry, 2012

2011

Lines in higher dimensions

Natan Rubin

PhD thesis, 2011

2010

Line Transversals of Convex Polyhedra in R³.

Haim Kaplan, Natan Rubin, Micha Sharir

SIAM J. Comput., 2010

Improved Bounds for Geometric Permutations.

Natan Rubin, Haim Kaplan, Micha Sharir

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Lines avoiding balls in three dimensions revisited.

Natan Rubin

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

A kinetic triangulation scheme for moving points in the plane.

Haim Kaplan, Natan Rubin, Micha Sharir

Proceedings of the 26th ACM Symposium on Computational Geometry, 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

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

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

Haim Kaplan, Natan Rubin, Micha Sharir

Proceedings of the Algorithms, 2007