research
∙
07/27/2023
The Unweighted and Weighted Reverse Shortest Path Problem for Disk Graphs
We study the reverse shortest path problem on disk graphs in the plane. ...
share
research
∙
12/06/2022
Improved Algebraic Degeneracy Testing
In the classical linear degeneracy testing problem, we are given n real ...
research
∙
08/13/2022
Intersection Searching amid Tetrahedra in Four Dimensions
We develop data structures for intersection queries in four dimensions t...
research
∙
05/12/2022
Bottleneck Matching in the Plane
We present an algorithm for computing a bottleneck matching in a set of ...
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
∙
11/03/2021
Efficient algorithms for optimization problems involving distances in a point set
We present a general technique, based on parametric search with some twi...
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
∙
02/15/2021
On Ray Shooting for Triangles in 3-Space and Related Problems
We consider several problems that involve lines in three dimensions, and...
research
∙
02/08/2021
Throwing a Sofa Through the Window
We study several variants of the problem of moving a convex polytope K, ...
research
∙
12/22/2020
On rich points and incidences with restricted sets of lines in 3-space
Let L be a set of n lines in R^3 that is contained, when represented as ...
research
∙
12/08/2020
On rich lenses in planar arrangements of circles and related problems
We show that the maximum number of pairwise non-overlapping k-rich lense...
research
∙
07/07/2020
Incidences with curves in three dimensions
We study incidence problems involving points and curves in R^3. The curr...
research
∙
06/22/2020
Duality-based approximation algorithms for depth queries and maximum depth
We design an efficient data structure for computing a suitably defined a...
research
∙
06/08/2020
Space-Aware Reconfiguration
We consider the problem of reconfiguring a set of physical objects into ...
research
∙
05/17/2020
Output sensitive algorithms for approximate incidences and their applications
An ϵ-approximate incidence between a point and some geometric object (li...
research
∙
05/11/2020
On Radial Isotropic Position: Theory and Algorithms
We review the theory of, and develop algorithms for transforming a finit...
research
∙
03/30/2020
How to Find a Point in the Convex Hull Privately
We study the question of how to compute a point in the convex hull of an...
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/04/2020
Incidences between points and curves with almost two degrees of freedom
We study incidences between points and algebraic curves in three dimensi...
research
∙
03/01/2020
The Maximum-Level Vertex in an Arrangement of Lines
Let L be a set of n lines in the plane, not necessarily in general posit...
research
∙
07/03/2019
Triangles and Girth in Disk Graphs and Transmission Graphs
Let S ⊂R^2 be a set of n sites, where each s ∈ S has an associated radiu...
research
∙
03/17/2019
General techniques for approximate incidences and their application to the camera posing problem
We consider the classical camera pose estimation problem that arises in ...
research
∙
10/24/2018
Approximate Minimum-Weight Matching with Outliers under Translation
Our goal is to compare two planar point sets by finding subsets of a giv...
research
∙
01/09/2018
Stabbing pairwise intersecting disks by five points
We present an O(n) expected time algorithm and an O(n n) deterministic ...
research
∙
12/08/2017
Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
We re-examine parameters for the two main space decomposition technique...
research
∙
09/09/2017