research
∙
06/29/2023
Oriented Spanners
Given a point set P in the Euclidean plane and a parameter t, we define ...
share
research
∙
10/11/2022
Morphing Planar Graph Drawings Through 3D
In this paper, we investigate crossing-free 3D morphs between planar str...
research
∙
05/16/2022
Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds
We consider the unlabeled motion-planning problem of m unit-disc robots ...
research
∙
03/14/2022
On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem
We consider the following surveillance problem: Given a set P of n sites...
research
∙
03/09/2022
Computing Continuous Dynamic Time Warping of Time Series in Polynomial Time
Dynamic Time Warping is arguably the most popular similarity measure for...
research
∙
01/10/2022
Segment Visibility Counting Queries in Polygons
Let P be a simple polygon with n vertices, and let A be a set of m point...
research
∙
06/22/2021
Near-Delaunay Metrics
We study metrics that assess how close a triangulation is to being a Del...
research
∙
05/20/2021
Computing the Fréchet Distance Between Uncertain Curves in One Dimension
We consider the problem of computing the Fréchet distance between two cu...
research
∙
05/06/2021
Dots Boxes is PSPACE-complete
Exactly 20 years ago at MFCS, Demaine posed the open problem whether the...
research
∙
03/26/2021
Minimum Scan Cover and Variants – Theory and Experiments
We consider a spectrum of geometric optimization problems motivated by c...
research
∙
03/16/2021
Uncertain Curve Simplification
We study the problem of polygonal curve simplification under uncertainty...
research
∙
12/01/2020
(k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time Warping
Due to the massively increasing amount of available geospatial data and ...
research
∙
05/05/2020
Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency
We consider the problem of finding patrol schedules for k robots to visi...
research
∙
04/24/2020
Fréchet Distance for Uncertain Curves
In this paper we study a wide range of variants for computing the (discr...
research
∙
04/02/2020
Dots Polygons
We present a new game, Dots Polygons, played on a planar point set. ...
research
∙
12/03/2019
Sometimes Reliable Spanners of Almost Linear Size
Reliable spanners can withstand huge failures, even when a linear number...
research
∙
02/21/2019
On the hardness of computing an average curve
We study the complexity of clustering curves under k-median and k-center...
research
∙
11/16/2018
A Spanner for the Day After
We show how to construct (1+ε)-spanner over a set P of n points in R^d t...
research
∙
07/23/2018
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...
research
∙
06/07/2018
Progressive Simplification of Polygonal Curves
Simplifying polygonal curves at different levels of detail is an importa...
research
∙
05/03/2018
Approximating (k,ℓ)-center clustering for curves
The Euclidean k-center problem is a classical problem that has been exte...
research
∙
03/23/2018
O(k)-robust spanners in one dimension
A geometric t-spanner on a set of points in Euclidean space is a graph c...
research
∙
07/05/2017
Placing your Coins on a Shelf
We consider the problem of packing a family of disks "on a shelf", that ...
research
∙
05/17/2017