Micha Sharir | DeepAI

AI Chat

Featured Co-authors

Haim Kaplan
52 publications
Sariel Har-Peled
44 publications
Uri Stemmer
37 publications
Wolfgang Mulzer
32 publications
Jean Cardinal
27 publications
Dan Halperin
26 publications
Mark de Berg
24 publications
John Iacono
24 publications
Pankaj K. Agarwal
22 publications
Kurt Mehlhorn
21 publications
Eunjin Oh
20 publications

∙ 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. ...

0 Haim Kaplan, et al. ∙

∙ 12/06/2022

Improved Algebraic Degeneracy Testing

In the classical linear degeneracy testing problem, we are given n real ...

0 Jean Cardinal, et al. ∙

∙ 08/13/2022

Intersection Searching amid Tetrahedra in Four Dimensions

We develop data structures for intersection queries in four dimensions t...

0 Esther Ezra, et al. ∙

∙ 05/12/2022

Bottleneck Matching in the Plane

We present an algorithm for computing a bottleneck matching in a set of ...

0 Matthew J. Katz, et al. ∙

∙ 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...

0 Pankaj K. Agarwal, et al. ∙

∙ 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...

0 Matthew J. Katz, et al. ∙

∙ 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 ...

0 Boris Aronov, et al. ∙

∙ 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...

0 Esther Ezra, et al. ∙

∙ 02/08/2021

Throwing a Sofa Through the Window

We study several variants of the problem of moving a convex polytope K, ...

0 Dan Halperin, et al. ∙

∙ 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 ...

0 Micha Sharir, et al. ∙

∙ 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...

0 Esther Ezra, et al. ∙

∙ 07/07/2020

Incidences with curves in three dimensions

We study incidence problems involving points and curves in R^3. The curr...

0 Micha Sharir, et al. ∙

∙ 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...

0 Dror Aiger, et al. ∙

∙ 06/08/2020

Space-Aware Reconfiguration

We consider the problem of reconfiguring a set of physical objects into ...

0 Dan Halperin, et al. ∙

∙ 05/17/2020

Output sensitive algorithms for approximate incidences and their applications

An ϵ-approximate incidence between a point and some geometric object (li...

0 Dror Aiger, et al. ∙

∙ 05/11/2020

On Radial Isotropic Position: Theory and Algorithms

We review the theory of, and develop algorithms for transforming a finit...

0 Shiri Artstein-Avidan, et al. ∙

∙ 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...

0 Haim Kaplan, et al. ∙

∙ 03/21/2020

Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets

We present subquadratic algorithms, in the algebraic decision-tree model...

0 Boris Aronov, et al. ∙

∙ 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...

0 Micha Sharir, et al. ∙

∙ 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...

0 Dan Halperin, et al. ∙

∙ 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...

0 Haim Kaplan, et al. ∙

∙ 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 ...

0 Dror Aiger, et al. ∙

∙ 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...

0 Pankaj K. Agarwal, et al. ∙

∙ 01/09/2018

Stabbing pairwise intersecting disks by five points

We present an O(n) expected time algorithm and an O(n n) deterministic ...

0 Sariel Har-Peled, et al. ∙

∙ 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...

0 Esther Ezra, et al. ∙

∙ 09/09/2017

Homotheties and incidences

We consider problems involving rich homotheties in a set S of n points i...

0 Dror Aiger, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world