Fast greedy algorithms for constructing sparse geometric spanners
Gudmundsson, J ; Levcopoulos, Christos LU
and Narasimhan, G
(2002)
In SIAM Journal on Computing
31(5).
p.1479-1500
- Abstract
- Given a set V of n points in R-d and a real constant t > 1, we present the first O(n log n)-time algorithm to compute a geometric t-spanner on V. A geometric t-spanner 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:
https://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
- Society for Industrial and Applied Mathematics
- external identifiers
-
- wos:000178000900010
- scopus:0036588760
- ISSN
- 0097-5397
- DOI
- 10.1137/S0097539700382947
- language
- English
- LU publication?
- yes
- id
- 001bc5c1-af26-4ec1-a682-10492797ae62 (old id 328491)
- date added to LUP
- 2016-04-01 16:59:16
- date last changed
- 2022-04-23 01:54:09
@article{001bc5c1-af26-4ec1-a682-10492797ae62,
abstract = {{Given a set V of n points in R-d and a real constant t > 1, we present the first O(n log n)-time algorithm to compute a geometric t-spanner on V. A geometric t-spanner 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 = {{0097-5397}},
keywords = {{sparse geometric spanners; cluster graph; computational geometry}},
language = {{eng}},
number = {{5}},
pages = {{1479--1500}},
publisher = {{Society for Industrial and Applied Mathematics}},
series = {{SIAM Journal on Computing}},
title = {{Fast greedy algorithms for constructing sparse geometric spanners}},
url = {{http://dx.doi.org/10.1137/S0097539700382947}},
doi = {{10.1137/S0097539700382947}},
volume = {{31}},
year = {{2002}},
}