research
∙
09/05/2023
From Curves to Words and Back Again: Geometric Computation of Minimum-Area Homotopy
Let γ be a generic closed curve in the plane. Samuel Blank, in his 1967 ...
share
research
∙
07/31/2023
Shortcut Partitions in Minor-Free Graphs: Steiner Point Removal, Distance Oracles, Tree Covers, and More
The notion of shortcut partition, introduced recently by Chang, Conroy, ...
research
∙
06/09/2023
Resolving the Steiner Point Removal Problem in Planar Graphs via Shortcut Partitions
Recently the authors [CCLMST23] introduced the notion of shortcut partit...
research
∙
06/09/2023
Covering Planar Metrics (and Beyond): O(1) Trees Suffice
While research on the geometry of planar graphs has been active in the p...
research
∙
06/21/2022
Near-Linear ε-Emulators for Planar Graphs
We study vertex sparsification for distances, in the setting of planar g...
research
∙
04/08/2022
Deterministic, Near-Linear ε-Approximation Algorithm for Geometric Bipartite Matching
Given point sets A and B in ℝ^d where A and B have equal size n for some...
research
∙
09/30/2020
Clustering under Perturbation Stability in Near-Linear Time
We consider the problem of center-based clustering in low-dimensional Eu...
research
∙
03/02/2020
Tightening Curves on Surfaces Monotonically with Applications
We prove the first polynomial bound on the number of monotonic homotopy ...
research
∙
02/29/2020
Dynamic geometric set cover and hitting set
We investigate dynamic versions of geometric set cover and hitting set w...
research
∙
03/22/2019
Efficient Algorithms for Geometric Partial Matching
Let A and B be two point sets in the plane of sizes r and n respectively...
research
∙
07/04/2018
Near-Optimal Distance Emulator for Planar Graphs
Given a graph G and a set of terminals T, a distance emulator of G is an...
research
∙
07/15/2017