
Subquadratic Algorithms for Some 3SumHard Geometric Problems in the Algebraic Decision Tree Model
We present subquadratic algorithms in the algebraic decisiontree model ...
read it

On Ray Shooting for Triangles in 3Space and Related Problems
We consider several problems that involve lines in three dimensions, and...
read it

Throwing a Sofa Through the Window
We study several variants of the problem of moving a convex polytope K, ...
read it

On rich points and incidences with restricted sets of lines in 3space
Let L be a set of n lines in R^3 that is contained, when represented as ...
read it

On rich lenses in planar arrangements of circles and related problems
We show that the maximum number of pairwise nonoverlapping krich lense...
read it

Incidences with curves in three dimensions
We study incidence problems involving points and curves in R^3. The curr...
read it

Dualitybased approximation algorithms for depth queries and maximum depth
We design an efficient data structure for computing a suitably defined a...
read it

SpaceAware Reconfiguration
We consider the problem of reconfiguring a set of physical objects into ...
read it

Output sensitive algorithms for approximate incidences and their applications
An ϵapproximate incidence between a point and some geometric object (li...
read it

On Radial Isotropic Position: Theory and Algorithms
We review the theory of, and develop algorithms for transforming a finit...
read it

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...
read it

Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets
We present subquadratic algorithms, in the algebraic decisiontree model...
read it

Incidences between points and curves with almost two degrees of freedom
We study incidences between points and algebraic curves in three dimensi...
read it

The MaximumLevel Vertex in an Arrangement of Lines
Let L be a set of n lines in the plane, not necessarily in general posit...
read it

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...
read it

General techniques for approximate incidences and their application to the camera posing problem
We consider the classical camera pose estimation problem that arises in ...
read it

Approximate MinimumWeight Matching with Outliers under Translation
Our goal is to compare two planar point sets by finding subsets of a giv...
read it

Stabbing pairwise intersecting disks by five points
We present an O(n) expected time algorithm and an O(n n) deterministic ...
read it

Decomposing arrangements of hyperplanes: VCdimension, combinatorial dimension, and point location
We reexamine parameters for the two main space decomposition technique...
read it

Homotheties and incidences
We consider problems involving rich homotheties in a set S of n points i...
read it
Micha Sharir
is this you? claim profile