Longueur d'arête la plus longue de la clé gourmande sur des ensembles de points uniformément répartis dans

Soit un ensemble de points dans . Pour tout , une clé est un graphique non orienté pondéré sous la mesure euclidienne, de sorte que pour deux points , , la distance la plus courte en , , est au plus fois la distance euclidienne entre et ,(notez que cette définition peut facilement être étendue à des espaces de mesures arbitraires). $P$ $N$ $\mathbb{R}^d$ $t \geq 1$ $t$ $G=(P, E)$ $v$ $u$ $G$ $d(v, u)$ $t$ $v$ $u$ $|v u|$

Considérez l'algorithme suivant avec et en entrée: $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

Cet algorithme calcule la clé dite gourmande (ou clé path-gourmande). Ce graphique a fait l'objet de recherches considérables: il produit des clés extrêmement bonnes, à la fois en pratique et en théorie.

Je m'intéresse à la longueur du bord le plus long de la clé gourmande si est uniformément distribué dans (le cas où d = 2 est bien aussi). Je suppose que cette longueur maximale est au maximum d'environ , potentiellement avec certains facteurs logarithmiques et les facteurs . Cette conjecture est motivée par des données expérimentales. $P$ $[0,1]^d$ $1 / \sqrt{N}$ $d$

La raison de mon intérêt est que j'ai un algorithme qui calcule rapidement la clé gourmande si la longueur du bord le plus long est relativement courte. Si ce qui précède est correct, cela signifierait que mon algorithme est applicable au scénario ci-dessus, et donc potentiellement utile dans la pratique.

J'ai trouvé des articles analysant le nombre d'arêtes et le degré d'autres types de clés sur des ensembles de points répartis de manière aléatoire, mais aucun sur la longueur de l'arête la plus longue. La théorie des probabilités impliquée semblait plutôt compliquée, alors j'espérais que quelque chose était connu avant d'essayer moi-même une preuve.

cg.comp-geom Alex ten Brink
la source

Dans notre article Construction sensible à la distribution de la clé gourmande (acceptée pour l'ESA 2014), nous prouvons ce qui suit (combinant le théorème 4 et le lemme 6):

Il existe dépendant uniquement de tel que pour tout , si est un ensemble de points uniformément et indépendamment répartis de façon aléatoire dans un carré et est assez grand, alors avec une probabilité d'au moins , la clé cupide sur n'a pas de bords plus longs que . $c_t$ $t$ $c > 0$ $P$ $\sqrt{n} \times \sqrt{n}$ $n$ $1 - n^c$ $t$ $P$ $c \cdot c_t \log n$

Notre limite sur est assez grande, mais nous avons des preuves expérimentales que la «bonne» limite est . $c_t$ $\frac{1}{\sqrt[4]{t-1}} \cdot \frac{\log n}{\log \log n}$

Alex ten Brink
la source

Longueur d'arête la plus longue de la clé gourmande sur des ensembles de points uniformément répartis dans

Réponses: