The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Fast greedy algorithms for constructing sparse geometric spanners

På svenska

Author

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.

Department/s

  • Computer Science

Publishing year

2002

Language

English

Pages

1479-1500

Publication/Series

SIAM Journal on Computing

Volume

31

Issue

5

Document type

Journal article

Publisher

Society for Industrial and Applied Mathematics

Topic

  • Computer Science

Keywords

  • sparse geometric spanners
  • cluster graph
  • computational geometry

Status

Published

ISBN/ISSN/Other

  • ISSN: 0097-5397