research
∙
07/15/2020
Approximating the (continuous) Fréchet distance
We describe the first strongly subquadratic time algorithm with subexpon...
share
research
∙
10/09/2019
Minimum Cuts in Surface Graphs
We describe algorithms to efficiently compute minimum (s,t)-cuts and glo...
research
∙
10/02/2019
Approximating the Geometric Edit Distance
Edit distance is a measurement of similarity between two sequences such ...
research
∙
07/09/2019
A near-linear time approximation scheme for geometric transportation with arbitrary supplies and spread
The geometric transportation problem takes as input a set of points P in...
research
∙
07/09/2019
A near-linear time approximation scheme for geometric transportation with real supplies
The geometric transportation problem takes as input a set of points P in...
research
∙
03/19/2019
Faster Algorithms for the Geometric Transportation Problem
Let R and B be two point sets in R^d, with |R|+ |B| = n and where d is a...
research
∙
04/03/2018
Holiest Minimum-Cost Paths and Flows in Surface Graphs
Let G be an edge-weighted directed graph with n vertices embedded on an ...
research
∙
06/09/2017