7 papers
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 com…
Net and Prune: A Linear Time Algorithm for Euclidean Distance Problems
Sariel Har-Peled, Banjamin Raichel
We provide a general framework for getting expected linear time constant factor approximations (and in many cases FPTASs) to several well-known problems in Computational Geometry,…
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…
Preprocessing Uncertain Data into Supersequences for Sorting and Gaps
Maarten Löffler, Benjamin Raichel
In the preprocessing framework for dealing with uncertain data, one is given a set of regions that one is allowed to preprocess to create some auxiliary structure such that when a…
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…
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…