Meny

Du är här

Fast greedy algorithms for constructing sparse geometric spanners

Författare:
Publiceringsår: 2002
Språk: Engelska
Sidor: 1479-1500
Publikation/Tidskrift/Serie: SIAM journal on computing
Volym: 31
Nummer: 5
Dokumenttyp: Artikel
Förlag: SIAM PUBLICATIONS

Sammanfattning

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.

Disputation

Nyckelord

  • Technology and Engineering
  • sparse geometric spanners
  • cluster graph
  • computational geometry

Övriga

Published
Yes
  • ISSN: 0097-5397

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen