1 citations · 1 across the 4 of their papers we have counts for
12 papers · 1 filter
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…
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,…
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…