Låt V vara en uppsättning n punkter i 3-dimensionell Euclidean utrymme. En subgraph av den kompletta Euclidean grafen är en t-spanner om för någon u och v i V, längden på den kortaste vägen från u till v i spannern är som mest t gånger d (u, v). Vi visar att för alla t > 1, en girig algoritm producerar en t-spanner med O (n) kanter, och total egg vikt O(1). Tot(it4ST), där MST är ett minsta spännträd av V.
Ett viktigt resultat är att för alla konstant-dimensionella Euclidean metrisk och alla ε > 0, det finns en (1 + ε)-spanner med lätthet O(1) REF.
Optimally sparse spanners in 3-dimensional Euclidean space
{'venue': "SCG '93", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}