158 citations · 543 across the 80 of their papers we have counts for
5 papers · 1 filter
How to Find a Point in the Convex Hull Privately
Haim Kaplan, Micha Sharir, Uri Stemmer
We study the question of how to compute a point in the convex hull of an input set of points in in a differentially private manner. This question, which is…
Voronoi diagrams on planar graphs, and computing the diameter in deterministic time
Paweł Gawrychowski, Haim Kaplan, Shay Mozes +2
We present an explicit and efficient construction of additively weighted Voronoi diagrams on planar graphs. Let be a planar graph with vertices and sites that lie on a…
Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier
Omer Gold, Micha Sharir
Dynamic Time Warping (DTW) and Geometric Edit Distance (GED) are basic similarity measures between curves or general temporal sequences (e.g., time series) that are represented as…
Dominance Product and High-Dimensional Closest Pair under
Omer Gold, Micha Sharir
Given a set of points in , the Closest Pair problem is to find a pair of distinct points in at minimum distance. When is constant, there are efficient…
Improved Bounds for 3SUM, -SUM, and Linear Degeneracy
Omer Gold, Micha Sharir
Given a set of real numbers, the 3SUM problem is to decide whether there are three of them that sum to zero. Until a recent breakthrough by Grønlund and Pettie [FOCS'14], a sim…