Constructing Plane Spanners of Bounded Degree and Low
Weight |
| |
| Authors: | Prosenjit Bose Joachim Gudmundsson Michiel Smid |
| |
| Affiliation: | (1) School of Computer Science, Carleton University, Ottawa, Ontario, K1S 5B6, Canada;(2) Department of Mathematics and Computing Science, TU Eindhoven, P.O. Box 513, 5600 MB Eindhoven, The Netherlands |
| |
| Abstract: | Given a set S of n points in the plane, we give an O(n log
n)-time algorithm that constructs a plane t-spanner for S, with
t ≈ 10, such that the degree of each point of S is
bounded from above by 27, and the total edge length is proportional
to the weight of a minimum spanning tree of S. Previously, no
algorithms were known for constructing plane t-spanners of bounded
degree. |
| |
| Keywords: | Computational geometry Spanners Planar graphs Bounded degree graphs Low weight graphs |
| 本文献已被 SpringerLink 等数据库收录！ |
|
