7 citations · 31 across the 12 of their papers we have counts for
13 papers
Pattern Matching in Doubling Spaces
Corentin Allair, Antoine Vigneron
We consider the problem of matching a metric space of size with a subspace of a metric space of size , assuming that these two spaces have constan…
Faster Algorithms for Growing Prioritized Disks and Rectangles
Hee-Kap Ahn, Sang Won Bae, Jongmin Choi +6
Motivated by map labeling, Funke, Krumpe, and Storandt [IWOCA 2016] introduced the following problem: we are given a sequence of disks in the plane. Initially, all disks have r…
Improved Bounds for Beacon-Based Coverage and Routing in Simple Rectilinear Polygons
Sang Won Bae, Chan-Su Shin, Antoine Vigneron
We establish tight bounds for beacon-based coverage problems, and improve the bounds for beacon-based routing problems in simple rectilinear polygons. Specifically, we show that $\…
A Faster Algorithm for Computing Straight Skeletons
Siu-Wing Cheng, Liam Mencel, Antoine Vigneron
We present a new algorithm for computing the straight skeleton of a polygon. For a polygon with vertices, among which are reflex vertices, we give a deterministic algorithm…
A Faster Algorithm for Computing Motorcycle Graphs
Antoine Vigneron, Lie Yan
We present a new algorithm for computing motorcycle graphs that runs in O(n^(4/3+e)) time for any e>0, improving on all previously known algorithms. The main application of this re…
Computing the Gromov hyperbolicity of a discrete metric space
Hervé Fournier, Anas Ismail, Antoine Vigneron
We give exact and approximation algorithms for computing the Gromov hyperbolicity of an n-point discrete metric space. We observe that computing the Gromov hyperbolicity from a fix…