| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 6868512 | Computational Geometry | 2018 | 20 Pages |
Abstract
We study the geometric properties of minimum RBP spanning graphs and the algorithmic problems associated with computing them. Specifically, we show that the general problem can be solved in polynomial time using matroid techniques. In addition, we discuss more efficient algorithms for the case in which points are located on a line or a circle, and also describe a fast (12Ï+1)-approximation algorithm, where Ï is the Steiner ratio.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ferran Hurtado, Matias Korman, Marc van Kreveld, Maarten Löffler, Vera Sacristán, Akiyoshi Shioura, Rodrigo I. Silveira, Bettina Speckmann, Takeshi Tokuyama,