Наибольшая длина ребра жадного гаечного ключа на равномерно распределенных точках в

10

Пусть - множество из N точек в R d . Для любого т 1 , A т -spanner представляет собой неориентированный граф G = ( Р , Е ) , взвешенный в соответствии с евклидовыми мерами, таким , что для любых двух точек V , U , самое короткое расстояние в G , d ( v , у ) , не более чем в t раз евклидово расстояние между v и u , | v u |PNRdt1tG=(P,E)vuGd(v,u)tvu|vu| (обратите внимание, что это определение можно легко распространить на произвольные пространства мер).

Рассмотрим следующий алгоритм с и t в качестве входных данных:Pt

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

Этот алгоритм вычисляет так называемый жадный гаечный ключ (или жадный ключ пути). Этот график подвергся значительным исследованиям: он дает чрезвычайно хорошие ключи, как на практике, так и в теории.

Меня интересует длина самого длинного края жадного гаечного ключа, если равномерно распределен в [ 0 , 1 ] d (случай, когда d = 2 также подходит). Я предполагаю, что максимальная длина не более 1 / P[0,1]d , потенциально с некоторыми логарифмическими факторами и факторамиd. Эта гипотеза обоснована экспериментальными данными.1/Nd

Причина моего интереса в том, что у меня есть алгоритм, который быстро вычисляет жадный гаечный ключ, если длина самого длинного края относительно мала. Если вышеприведенное верно, то это будет означать, что мой алгоритм применим к описанному выше сценарию и поэтому потенциально полезен на практике.

Я нашел несколько работ, анализирующих количество ребер и степень других типов гаечных ключей на случайно распределенных точках, но ни одного на длине самого длинного ребра. Теория вероятностей казалась довольно сложной, поэтому я надеялся, что что-то было известно, прежде чем пытаться доказать это сам

Алекс тен Бринк
источник

Ответы:

4

В нашей статье « Чувствительная к распределению конструкция жадного гаечного ключа» (принята для ESA 2014) мы доказываем следующее (объединяя теорему 4 и лемму 6):

Существует зависящий только от t, такой что для каждого c > 0 , если P - множество точек, равномерно и независимо распределенных случайным образом в a cttc>0Pn×nn1nctPcctlogn

ct1t14lognloglogn

Алекс тен Бринк
источник