48 citations · 101 across the 24 of their papers we have counts for
30 papers · 1 filter
A Clique-Based Separator for Intersection Graphs of Geodesic Disks in
Boris Aronov, Mark de Berg, Leonidas Theocharous
Let be a (well-behaved) shortest-path metric defined on a path-connected subset of and let be a set of geodesic disks with respe…
Partitioning axis-parallel lines in 3D
Boris Aronov, Abdul Basit, Mark de Berg +1
Let be a set of axis-parallel lines in . We are are interested in partitions of by a set of three planes such that each open cell in the ar…
Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems
Pankaj K. Agarwal, Boris Aronov, Esther Ezra +2
Let be a set of flat (planar) semi-algebraic regions in of constant complexity (e.g., triangles, disks), which we call plates. We wish to preproces…
Subquadratic Algorithms for Some \textsc{3Sum}-Hard Geometric Problems in the Algebraic Decision Tree Model
Boris Aronov, Mark de Berg, Jean Cardinal +3
We present subquadratic algorithms in the algebraic decision-tree model for several \textsc{3Sum}-hard geometric problems, all of which can be reduced to the following question: Gi…
On Two-Handed Planar Assembly Partitioning with Connectivity Constraints
Pankaj K. Agarwal, Boris Aronov, Tzvika Geft +1
Assembly planning is a fundamental problem in robotics and automation, which involves designing a sequence of motions to bring the separate constituent parts of a product into thei…
Geometric Pattern Matching Reduces to k-SUM
Boris Aronov, Jean Cardinal
We prove that some exact geometric pattern matching problems reduce in linear time to -SUM when the pattern has a fixed size . This holds in the real RAM model for searching…
Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets: Collinearity Testing and Related Problems
Boris Aronov, Esther Ezra, Micha Sharir
We present subquadratic algorithms, in the algebraic decision-tree model of computation, for detecting whether there exists a triple of points, belonging to three respective sets $…
On beta-Plurality Points in Spatial Voting Games
Boris Aronov, Mark de Berg, Joachim Gudmundsson +1
Let be a set of points in , called voters. A point is a plurality point for when the following holds: for every the…
Efficient Nearest-Neighbor Query and Clustering of Planar Curves
Boris Aronov, Omrit Filtser, Michael Horton +2
We study two fundamental problems dealing with curves in the plane, namely, the nearest-neighbor problem and the center problem. Let be a set of polygonal curves,…
Constructive Polynomial Partitioning for Algebraic Curves in with Applications
Boris Aronov, Esther Ezra, Joshua Zahl
In 2015, Guth proved that for any set of -dimensional bounded complexity varieties in and for any positive integer , there exists a polynomial of degree at mos…
An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
Pankaj K. Agarwal, Boris Aronov, Esther Ezra +1
In 2015, Guth proved that if is a collection of -dimensional semi-algebraic sets in and if is an integer, then there is a -variate polynomial…
Resolving SINR Queries in a Dynamic Setting
Boris Aronov, Gali Bar-On, Matthew J. Katz
We consider a set of transmitters broadcasting simultaneously on the same frequency under the SINR model. Transmission power may vary from one transmitter to another, and a transmi…
On Pseudo-disk Hypergraphs
Boris Aronov, Anirudh Donakonda, Esther Ezra +1
Let be a family of pseudo-disks in the plane, and be a finite subset of . Consider the hypergraph whose vertices are the pseudo-disks in and the edges are a…
Eliminating Depth Cycles among Triangles in Three Dimensions
Boris Aronov, Edward Y. Miller, Micha Sharir
Given pairwise openly disjoint triangles in 3-space, their vertical depth relation may contain cycles. We show that, for any , the triangles can be cut into $O(n…
Nearest-Neighbor Searching Under Uncertainty II
Pankaj K. Agarwal, Boris Aronov, Sariel Har-Peled +3
Nearest-neighbor search, which returns the nearest neighbor of a query point in a set of points, is an important and widely studied problem in many fields, and it has wide range of…
Distance-Sensitive Planar Point Location
Boris Aronov, Mark de Berg, David Eppstein +2
Let be a connected planar polygonal subdivision with edges that we want to preprocess for point-location queries, and where we are given the probability tha…
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…
Batched Point Location in SINR Diagrams via Algebraic Tools
Boris Aronov, Matthew J. Katz
The SINR model for wireless networks has been extensively studied recently. It tries to model whether a particular transmitter is heard at a specific location, with transmittin…
How To Place a Point to Maximize Angles
Boris Aronov, Mark V. Yagnatinsky
We describe a randomized algorithm that, given a set of points in the plane, computes the best location to insert a new point , such that the Delaunay triangulation of $P\cu…
Complexity of a Single Face in an Arrangement of s-Intersecting Curves
Boris Aronov, Dmitriy Drusvyatskiy
Consider a face F in an arrangement of n Jordan curves in the plane, no two of which intersect more than s times. We prove that the combinatorial complexity of F is O(λ_s(n)), O(λ_…
How to Cover a Point Set with a V-Shape of Minimum Width
Boris Aronov, Muriel Dulieu
A balanced V-shape is a polygonal region in the plane contained in the union of two crossing equal-width strips. It is delimited by two pairs of parallel rays that emanate from two…