Natan Rubin

activity

20082021

most citedOn Kinetic Delaunay Triangulations: A Near Quadratic Bound for Unit Speed Motions

3 citations · 9 across the 11 of their papers we have counts for

collaborators

15 papers

cs.CG2021

Stronger Bounds for Weak Epsilon-Nets in Higher Dimensions

Natan Rubin

Given a finite point set $P$ in $R^{d}$ , and $ε > 0$ we say that $N \subseteq R^{d}$ is a weak $ε$ -net if it pierces every convex set $K$ with $∣ K \cap P ∣ \geq ε ∣ P ∣$ . We…

math.CO2019

Planar Point Sets Determine Many Pairwise Crossing Segments

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

We show that any set of $n$ points in general position in the plane determines $n^{1 - o (1)}$ pairwise crossing segments. The best previously known lower bound, $Ω\left(\sqrt n\right…

math.CO2018

An Improved Bound for Weak Epsilon-Nets in the Plane

Natan Rubin

We show that for any finite set $P$ of points in the plane and $ε > 0$ there exist $O (\frac{1}{ε ^{3/2 + γ}})$ points in $R^{2}$ , for arbitrary small $…

math.CO2018

Further Consequences of the Colorful Helly Hypothesis

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

Let $F$ be a family of convex sets in $R^{d}$ , which are colored with $d + 1$ colors. We say that $F$ satisfies the Colorful Helly Property if every rainb…

math.CO2017

A Crossing Lemma for Jordan Curves

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

If two Jordan curves in the plane have precisely one point in common, and there they do not properly cross, then the common point is called a {\em touching point}. The main result…

cs.CG2015★ 1 cited

Stable Delaunay Graphs

Pankaj K. Agarwal, Jie Gao, Leonidas J. Guibas +3

Let $P$ be a set of $n$ points in $R^{2}$ , and let $DT (P)$ denote its Euclidean Delaunay triangulation. We introduce the notion of an edge of $DT (P)$ being…