Fast greedy algorithms for constructing sparse geometric spanners

Summary, in English

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.

• Författare: J Gudmundsson; Christos Levcopoulos; G Narasimhan
• Avdelning/ar: Computer Science
• Publiceringsår: 2002
• Språk: Engelska
• Sidor: 1479-1500
• Publikation/Tidskrift/Serie: SIAM Journal on Computing
• Volym: 31
• Issue: 5
• Länkar: http://dx.doi.org/10.1137/S0097539700382947
• Dokumenttyp: Artikel i tidskrift
• Förlag: Society for Industrial and Applied Mathematics
• Ämne: Computer Science
• Nyckelord: sparse geometric spanners; cluster graph; computational geometry
• Status: Published
• ISBN/ISSN/Övrigt: ISSN: 0097-5397