Fast greedy algorithms for constructing sparse geometric spanners
(2002) In SIAM Journal on Computing 31(5). p.14791500 Abstract
 Given a set V of n points in Rd and a real constant t > 1, we present the first O(n log n)time algorithm to compute a geometric tspanner on V. A geometric tspanner on V is a connected graph G = ( V, E) with edge weights equal to the Euclidean distances between the endpoints, and with the property that, for all u, v is an element of V the distance between u and v in G is at most t times the Euclidean distance between u and v. The spanner output by the algorithm has O(n) edges and weight O(1).wt (MST), and its degree is bounded by a constant.
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/328491
 author
 Gudmundsson, J; Levcopoulos, Christos ^{LU} and Narasimhan, G
 organization
 publishing date
 2002
 type
 Contribution to journal
 publication status
 published
 subject
 keywords
 sparse geometric spanners, cluster graph, computational geometry
 in
 SIAM Journal on Computing
 volume
 31
 issue
 5
 pages
 1479  1500
 publisher
 SIAM Publications
 external identifiers

 wos:000178000900010
 scopus:0036588760
 ISSN
 00975397
 DOI
 10.1137/S0097539700382947
 language
 English
 LU publication?
 yes
 id
 001bc5c1af264ec1a68210492797ae62 (old id 328491)
 date added to LUP
 20070822 08:21:08
 date last changed
 20170730 04:43:40
@article{001bc5c1af264ec1a68210492797ae62, abstract = {Given a set V of n points in Rd and a real constant t > 1, we present the first O(n log n)time algorithm to compute a geometric tspanner on V. A geometric tspanner on V is a connected graph G = ( V, E) with edge weights equal to the Euclidean distances between the endpoints, and with the property that, for all u, v is an element of V the distance between u and v in G is at most t times the Euclidean distance between u and v. The spanner output by the algorithm has O(n) edges and weight O(1).wt (MST), and its degree is bounded by a constant.}, author = {Gudmundsson, J and Levcopoulos, Christos and Narasimhan, G}, issn = {00975397}, keyword = {sparse geometric spanners,cluster graph,computational geometry}, language = {eng}, number = {5}, pages = {14791500}, publisher = {SIAM Publications}, series = {SIAM Journal on Computing}, title = {Fast greedy algorithms for constructing sparse geometric spanners}, url = {http://dx.doi.org/10.1137/S0097539700382947}, volume = {31}, year = {2002}, }