Comprimento de borda mais longo da chave de ganância em conjuntos de pontos uniformemente distribuídos em

Seja um conjunto de pontos em . Para qualquer , um -spanner é um grafo não direcionado ponderada sob a medida Euclidiana, de tal modo que para quaisquer dois pontos , , a distância mais curta em , , é no máximo vezes a distância euclidiana entre e ,(observe que essa definição pode ser facilmente estendida para espaços de medida arbitrários).N R d t ≥ 1 $P$$N$$\mathbb{R}^d$$t \geq 1$$t$v u G d ( v , u ) t v u | v u $G=(P, E)$$v$$u$$G$$d(v, u)$$t$$v$$u$$|v u|$

Considere o seguinte algoritmo com e como entrada:$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

Este algoritmo calcula a chamada chave de ganância (ou chave de caminho ganancioso). Este gráfico foi sujeito a uma pesquisa considerável: produz chaves inglesas extremamente boas, tanto na prática quanto na teoria.

Estou interessado no comprimento da borda mais longa da chave gananciosa, se for uniformemente distribuído em (o caso em que d = 2 também está bom). Suponho que esse comprimento máximo seja no máximo cerca de , potencialmente com alguns fatores de log e fatores . Essa conjectura é motivada por dados experimentais.[ 0 , 1 ] d 1 / $P$$[0,1]^d$$1 / \sqrt{N}$$d$

A razão do meu interesse é que eu tenho um algoritmo que calcula rapidamente a chave gananciosa se o comprimento da borda mais longa for relativamente curto. Se o exposto acima estiver correto, isso significaria que meu algoritmo é aplicável ao cenário acima e, portanto, potencialmente útil na prática.

Encontrei alguns trabalhos analisando o número de arestas e o grau de outros tipos de chaves inglesas em conjuntos de pontos distribuídos aleatoriamente, mas nenhum no comprimento da aresta mais longa. A teoria da probabilidade envolvida parecia bastante complicada, então eu esperava que algo fosse conhecido antes de tentar uma prova.

No nosso artigo Construção sensível à distribuição da chave gananciosa (aceito no SEC 2014), provamos o seguinte (combinando o Teorema 4 e o Lema 6):

Existe dependente apenas de tal modo que para cada , se é um conjunto de pontos uniformemente e de forma independente, distribuídos aleatoriamente em um quadrado e é suficientemente grande, então com probabilidade de pelo menos , o gancho gancho em não possui arestas maiores que . t c > 0 P $c_t$$t$$c > 0$$P$$\sqrt{n} \times \sqrt{n}$$n$$1 - n^c$$t$$P$$c \cdot c_t \log n$

Nosso limite em é bastante grande, mas temos evidências experimentais de que o limite "certo" é .$c_t$$\frac{1}{\sqrt[4]{t-1}} \cdot \frac{\log n}{\log \log n}$