Najdłuższa krawędź chciwego klucza w równomiernie rozmieszczonych zestawach punktów w

Niech będzie zbiorem punktów w . Dla każdego , A -spanner jest nieukierunkowane wykres odważony w euklidesowej mierze tak, że na jednym z dwóch punktów , najkrótsza odległość w , jest co najwyżej razy odległość euklidesową między i ,(zwróć uwagę, że definicję tę można łatwo rozszerzyć na dowolne przestrzenie miar).N R d t ≥ 1 t G = ( P , E ) v u G d ( v , u ) t v 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|$

Rozważ następujący algorytm z i jako danymi wejściowymi:$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

Ten algorytm oblicza tak zwany klucz zachłanny (lub klucz zachłanny ścieżką). Ten wykres został poddany znacznym badaniom: produkuje wyjątkowo dobre klucze, zarówno w praktyce, jak i w teorii.

Interesuje mnie długość najdłuższej krawędzi w zachłannym kluczu, jeśli jest równomiernie rozmieszczone w [ 0 , 1 ] d (w przypadku, gdy d = 2 jest również w porządku). Przypuszczam, że ta maksymalna długość wynosi najwyżej około 1 / $P$$[0,1]^d$ , potencjalnie z pewnymi współczynnikami log i czynnikamid. Ta hipoteza jest motywowana danymi eksperymentalnymi.$1 / \sqrt{N}$$d$

Powodem mojego zainteresowania jest to, że mam algorytm, który szybko oblicza zachłanny klucz, jeśli długość najdłuższej krawędzi jest stosunkowo krótka. Jeśli powyższe jest poprawne, oznaczałoby to, że mój algorytm ma zastosowanie do powyższego scenariusza, a zatem potencjalnie przydatny w praktyce.

Znalazłem kilka artykułów analizujących liczbę krawędzi i stopień innych typów kluczy w losowo rozmieszczonych zestawach punktów, ale żaden na długości najdłuższej krawędzi. Uwzględniona teoria prawdopodobieństwa wydawała się dość skomplikowana, więc miałem nadzieję, że coś się dowie, zanim sam spróbowałem udowodnić.

W naszym artykule Wrażliwa na rozkład konstrukcja chciwego klucza (przyjęta na ESA 2014) dowodzimy, co następuje (łącząc Twierdzenie 4 i Lemat 6):

Istnieje zależne tylko od t takie, że dla każdego c > 0 , jeżeli P jest zbiorem punktów równomiernie i niezależnie rozmieszczonych losowo w $c_t$$t$$c > 0$$P$ kwadrat injest wystarczająco duży, a następnie z prawdopodobieństwem co najmniej1-nc, zachłannyt-klucz naPnie ma krawędzi dłuższych niżc⋅ctlogn.$\sqrt{n} \times \sqrt{n}$$n$$1 - n^c$$t$$P$$c \cdot c_t \log n$

Nasz związany na jest dość duży, ale mamy dowody eksperymentalne, że „prawo” związany jest $c_t$ .$\frac{1}{\sqrt[4]{t-1}} \cdot \frac{\log n}{\log \log n}$