Med tanke på en metrisk M = (V, d), en graf G = (V, E) är en t-spanner för M om varje par noder i V har en "kort" väg (dvs. av längd som mest t gånger deras faktiska avstånd) mellan dem i spannern. Dessutom har denna skiftnyckel en humlediameter som begränsas av D om varje sådan kort väg också använder i de flesta D-kanter. Vi anser att problemet med att bygga sparse (1 + ε)-spanner med liten humlediameter för mått med låg dubblering dimension. I detta papper, visar vi att med tanke på varje metrisk med konstant dubblering dimension k, och alla 0 < ε < 1, kan man hitta en (1 + ε)-spanner för metrisken med nästan linjärt antal kanter (dvs. endast O(n log * n + nε −O(k) ) kanter) och en konstant humlediameter, och även en (1 + ε)-spanner med linjärt antal kanter (dvs. endast nε kanter) som uppnår en humlediameter som växer som den funktionella inversen av Ackermanns funktion. Dessutom bevisar vi att sådana avvägningar mellan antalet kanter och humlediametern är asymptotiskt optimala.
Specifikt visas det i REF att det för alla > 0 finns ett n-punkts Euclideans metriska utrymme M = M (n, ) för vilket alla Euclidean (1 + )-spanner med m-kanter har humlediameter (α(m, n)), där α är den funktionella inversen av Ackermanns funktion.
Small hop-diameter sparse spanners for doubling metrics
{'venue': "SODA '06", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}