Längste Kantenlänge des gierigen Schraubenschlüssels bei gleichmäßig verteilten Punktmengen in

Sei eine Menge von N Punkten in R d . Für jedes t ≥ 1 ist ein t- Schlüssel ein ungerichteter Graph G = ( P , E ), gewichtet nach dem euklidischen Maß, so dass für zwei beliebige Punkte v , u der kürzeste Abstand in G , d ( v , u ) , ist höchstens t mal der euklidische Abstand zwischen v und u , | v u $P$$N$$\mathbb{R}^d$$t \geq 1$$t$$G=(P, E)$$v$$u$$G$$d(v, u)$$t$$v$$u$$|v u|$ (Beachten Sie, dass diese Definition leicht auf beliebige Maßräume erweitert werden kann.)

Betrachten Sie den folgenden Algorithmus mit und t als Eingabe:$P$$t$

E = empty
for every pair of points (v, u) in ascending order under |vu|
    if the shortest path in (P, E) is more than t times |vu|
        add (v, u) to E
return E

Dieser Algorithmus berechnet den sogenannten Greedy Spanner (oder Path-Greedy Spanner). Dieser Graph wurde eingehend untersucht: Er liefert sowohl in der Praxis als auch in der Theorie äußerst gute Schraubenschlüssel.

Ich interessiere mich für die Länge der längsten Kante im gierigen Schraubenschlüssel, wenn in [ 0 , 1 ] d gleichmäßig verteilt ist (der Fall, dass d = 2 ist, ist ebenfalls in Ordnung). Ich vermute, dass diese maximale Länge höchstens etwa 1 / √ beträgt$P$$[0,1]^d$ , möglicherweise mit einigen logarithmischen Faktoren und Faktorend. Diese Vermutung ist durch experimentelle Daten motiviert.$1 / \sqrt{N}$$d$

Der Grund für mein Interesse ist, dass ich einen Algorithmus habe, der den gierigen Schraubenschlüssel schnell berechnet, wenn die Länge der längsten Kante relativ kurz ist. Wenn das oben Gesagte korrekt ist, würde dies bedeuten, dass mein Algorithmus auf das obige Szenario anwendbar und daher in der Praxis möglicherweise nützlich ist.

Ich habe einige Artikel gefunden, die die Anzahl der Kanten und den Grad anderer Arten von Schraubenschlüsseln auf zufällig verteilten Punktmengen analysieren, aber keine auf der Länge der längsten Kante. Die Wahrscheinlichkeitstheorie schien ziemlich kompliziert zu sein, also hoffte ich, dass etwas bekannt war, bevor ich selbst einen Beweis versuchte.

In unserer Arbeit Distribution-Sensitive Construction of the Greedy Spanner (angenommen für die ESA 2014) beweisen wir Folgendes (Kombination von Satz 4 und Lemma 6):

$c_t$$t$$c > 0$$P$$\sqrt{n} \times \sqrt{n}$$n$$1 - n^c$$t$$P$$c \cdot c_t \log n$

$c_t$$\frac{1}{\sqrt[4]{t-1}} \cdot \frac{\log n}{\log \log n}$