48 citations · 101 across the 24 of their papers we have counts for
4 papers · 2 filters
Almost Tight Bounds for Eliminating Depth Cycles in Three Dimensions
Boris Aronov, Micha Sharir
Given non-vertical lines in 3-space, their vertical depth (above/below) relation can contain cycles. We show that the lines can be cut into $O(n^{3/2}\mathop{\mathrm{polylog}}…
Time-Space Trade-off Algorithms for Triangulating a Simple Polygon
Boris Aronov, Matias Korman, Simon Pratt +2
An -workspace algorithm is an algorithm that has read-only access to the values of the input, write-only access to the output, and only uses additional words of space. We…
Fréchet Distance for Curves, Revisited
Boris Aronov, Sariel Har-Peled, Christian Knauer +2
$\renewcommand{\Re}{{\rm I\!\hspace{-0.025em} R}} \newcommand{\eps}{\varepsilon} \newcommand{\SetX}{\mathsf{X}} \newcommand{\VorX}[1]{\mathcal{V} \pth{#1}} \newcommand{\Polygon}{\m…
The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions
Boris Aronov, Otfried Cheong, Michael Gene Dobbins +1
We show that the union of translates of a convex body in can have holes in the worst case, where a hole in a set is a connected component of $\mathb…