7 citations · 11 across the 4 of their papers we have counts for
4 papers · 1 filter
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 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…
A Generalization of the Convex Kakeya Problem
Hee-Kap Ahn, Sang Won Bae, Otfried Cheong +3
Given a set of line segments in the plane, not necessarily finite, what is a convex region of smallest area that contains a translate of each input segment? This question can be se…
Computing k-Centers On a Line
Peter Brass, Christian Knauer, Hyeon-Suk Na +2
In this paper we consider several instances of the k-center on a line problem where the goal is, given a set of points S in the plane and a parameter k >= 1, to find k disks with c…