Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Fast greedy algorithms for constructing sparse geometric spanners

Gudmundsson, J ; Levcopoulos, Christos LU orcid 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:
author
; and
organization
publishing date
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}},
}