research
∙
04/04/2022
Partitioning axis-parallel lines in 3D
Let L be a set of n axis-parallel lines in ℝ^3. We are are interested in...
share
research
∙
03/19/2022
Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems
Let 𝒯 be a set of n planar semi-algebraic regions in ℝ^3 of constant com...
research
∙
09/15/2021
Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model
We present subquadratic algorithms in the algebraic decision-tree model ...
research
∙
09/25/2020
On Two-Handed Planar Assembly Partitioning
Assembly planning, which is a fundamental problem in robotics and automa...
research
∙
03/26/2020
Geometric Pattern Matching Reduces to k-SUM
We prove that some exact geometric pattern matching problems reduce in l...
research
∙
03/21/2020
Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets
We present subquadratic algorithms, in the algebraic decision-tree model...
research
∙
03/17/2020
On beta-Plurality Points in Spatial Voting Games
Let V be a set of n points in ℝ^d, called voters. A point p∈ℝ^d is a plu...
research
∙
04/24/2019
Efficient Nearest-Neighbor Query and Clustering of Planar Curves
We study two fundamental problems dealing with curves in the plane, name...
research
∙
04/21/2019
Constructive Polynomial Partitioning for Algebraic Curves in R^3 with Applications
In 2015, Guth proved that for any set of k-dimensional varieties in R^d ...
research
∙
12/26/2018
An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
Guth showed that given a family S of n g-dimensional semi-algebraic sets...
research
∙
05/07/2018
Non-Monochromatic and Conflict-Free Coloring on Tree Spaces and Planar Network Spaces
It is well known that any set of n intervals in R^1 admits a non-monochr...
research
∙
04/27/2018
Resolving SINR Queries in a Dynamic Setting
We consider a set of transmitters broadcasting simultaneously on the sam...
research
∙
02/24/2018
On Pseudo-disk Hypergraphs
Let F be a family of pseudo-disks in the plane, and P be a finite subset...
research
∙
06/30/2017