40 citations · 190 across the 39 of their papers we have counts for
53 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 comp…
A Constant-Factor Approximation for Continuous Dynamic Time Warping in 2D
Kevin Buchin, Maike Buchin, Jan Erik Swiadek +1
Continuous Dynamic Time Warping (CDTW) is a robust similarity measure for polygonal curves that has recently found a variety of applications. Despite its practical use, not much is…
Smallest Enclosing Disk Queries Using Farthest-Point Voronoi Diagrams
Kevin Buchin, Mark Joachim Krallmann, Frank Staals
Let be a set of points in . Our goal is to preprocess to efficiently compute the smallest enclosing disk of the points in that lie inside an axis-alig…
Reconfiguration of unit squares and disks: PSPACE-hardness in simple settings
Mikkel Abrahamsen, Kevin Buchin, Maike Buchin +5
We study two well-known reconfiguration problems. Given a start and a target configuration of geometric objects in a polygon, we wonder whether we can move the objects from the sta…
Orienteering (with Time Windows) on Restricted Graph Classes
Kevin Buchin, Mart Hagedoorn, Guangping Li +1
Given a graph with edge costs and vertex profits and given a budget B, the Orienteering Problem asks for a walk of cost at most B of maximum profit. Additionally, each profit may b…
Map-Matching Queries under Fréchet Distance on Low-Density Spanners
Kevin Buchin, Maike Buchin, Joachim Gudmundsson +2
Map matching is a common task when analysing GPS tracks, such as vehicle trajectories. The goal is to match a recorded noisy polygonal curve to a path on the map, usually represent…