11 citations · 15 across the 7 of their papers we have counts for
14 papers · 1 filter
Computing Planar Convex Hulls with a Promise
Sepideh Aghamolaei, Kevin Buchin, Timothy M. Chan +5
Computing the convex hull of a planar -point set is one of the most fundamental problems in computational geometry. It has an lower bound in the algebraic comp…
The Road to the Closest Point is Paved by Good Neighbors
Sariel Har-Peled, Benjamin Raichel, Eliot W. Robson
Given a set of points in , and a parameter , we present a new construction of a directed graph , of size $O…
Well-Separated Pairs Decomposition Revisited
Sariel Har-Peled, Benjamin Raichel, Eliot W. Robson
We revisit the notion of WSPD (i.e., well-separated pairs-decomposition), presenting a new construction of WSPD for any finite metric space, and show that it is asymptotically inst…
Preprocessing Disks for Convex Hulls, Revisited
Maarten Löffler, Benjamin Raichel
In the preprocessing framework one is given a set of regions that one is allowed to preprocess to create some auxiliary structure such that when a realization of these regions is g…
The Fréchet Distance Unleashed: Approximating a Dog with a Frog
Sariel Har-Peled, Benjamin Raichel, Eliot W. Robson
We show that a variant of the continuous Frechet distance between polygonal curves can be computed using essentially the same algorithm used to solve the discrete version. The new…
Fréchet Edit Distance
Emily Fox, Amir Nayyeri, Jonathan James Perry +1
We define and investigate the Fréchet edit distance problem. Given two polygonal curves and and a threshhold value , we seek the minimum number of edits to such th…