13 citations · 25 across the 15 of their papers we have counts for
5 papers · 1 filter
A Spanner for the Day After
Kevin Buchin, Sariel Har-Peled, Daniel Olah
We show how to construct -spanner over a set of points in that is resilient to a catastrophic failure of nodes. Specifically, for prescribed…
SETH Says: Weak Fréchet Distance is Faster, but only if it is Continuous and in One Dimension
Kevin Buchin, Tim Ophelders, Bettina Speckmann
We show by reduction from the Orthogonal Vectors problem that algorithms with strongly subquadratic running time cannot approximate the Fréchet distance between curves better than…
Progressive Simplification of Polygonal Curves
Kevin Buchin, Maximilian Konzack, Wim Reddingius
Simplifying polygonal curves at different levels of detail is an important problem with many applications. Existing geometric optimization algorithms are only capable of minimizing…
Approximating -center clustering for curves
Kevin Buchin, Anne Driemel, Joachim Gudmundsson +4
The Euclidean -center problem is a classical problem that has been extensively studied in computer science. Given a set of points in Euclidean space, the probl…
-robust spanners in one dimension
Kevin Buchin, Tim Hulshof, Dániel Oláh
A geometric -spanner on a set of points in Euclidean space is a graph containing for every pair of points a path of length at most times the Euclidean distance between the p…