
NearDelaunay Metrics
We study metrics that assess how close a triangulation is to being a Del...
read it

Computing the Fréchet Distance Between Uncertain Curves in One Dimension
We consider the problem of computing the Fréchet distance between two cu...
read it

Dots Boxes is PSPACEcomplete
Exactly 20 years ago at MFCS, Demaine posed the open problem whether the...
read it

Minimum Scan Cover and Variants – Theory and Experiments
We consider a spectrum of geometric optimization problems motivated by c...
read it

Uncertain Curve Simplification
We study the problem of polygonal curve simplification under uncertainty...
read it

(k, l)Medians Clustering of Trajectories Using Continuous Dynamic Time Warping
Due to the massively increasing amount of available geospatial data and ...
read it

Approximation Algorithms for MultiRobot PatrolScheduling with MinMax Latency
We consider the problem of finding patrol schedules for k robots to visi...
read it

Fréchet Distance for Uncertain Curves
In this paper we study a wide range of variants for computing the (discr...
read it

Dots Polygons
We present a new game, Dots Polygons, played on a planar point set. ...
read it

Sometimes Reliable Spanners of Almost Linear Size
Reliable spanners can withstand huge failures, even when a linear number...
read it

On the hardness of computing an average curve
We study the complexity of clustering curves under kmedian and kcenter...
read it

A Spanner for the Day After
We show how to construct (1+ε)spanner over a set P of n points in R^d t...
read it

SETH Says: Weak Fréchet Distance is Faster, but only if it is Continuous and in One Dimension
We show by reduction from the Orthogonal Vectors problem that algorithms...
read it

Progressive Simplification of Polygonal Curves
Simplifying polygonal curves at different levels of detail is an importa...
read it

Approximating (k,ℓ)center clustering for curves
The Euclidean kcenter problem is a classical problem that has been exte...
read it

O(k)robust spanners in one dimension
A geometric tspanner on a set of points in Euclidean space is a graph c...
read it

Placing your Coins on a Shelf
We consider the problem of packing a family of disks "on a shelf", that ...
read it

RangeClustering Queries
In a geometric kclustering problem the goal is to partition a set of po...
read it
Kevin Buchin
is this you? claim profile