Znajdź najkrótszą parą odległość punktów w o (n log n)?

Studenci, których nadzoruję, otrzymali następujące ćwiczenie:

Biorąc pod uwagę punktów na płaszczyźnie, opracuj algorytm, który znajdzie parę punktów, których odległość jest minimalna wśród wszystkich par punktów. Algorytm powinien działać w czasie .o ( N 2$n$$o(n^2)$

Istnieje (stosunkowo) prosty algorytm dzielenia i zdobywania, który rozwiązuje zadanie w czasie .$\Theta(n \log n)$

Pytanie 1 : Czy istnieje algorytm, który rozwiązuje dany problem dokładnie w najgorszym przypadku ?$\mathcal{o}(n \log n)$

Podejrzewałem, że może to być możliwe, wynik, który pamiętam z niektórych wystąpień (docenienie). Stwierdzono, że coś wzdłuż linii tego nie więcej niż stała liczba punktów może być ułożona w płaszczyźnie wokół jakiegoś punktu wewnątrz okręgu o promieniu , z minimalna odległość między dowolnymi dwoma zaangażowanymi punktami. Myślę , punkty tworzących sześciokąt równoboczny o w środku (w przypadku ekstremalnych). p r ∈ R r c = 7 $c \in \mathbb{N}$$p$$r \in \mathbb{R}$$r$$c=7$$p$

W takim przypadku następujący algorytm powinien rozwiązać problem w krokach.$n$

fun mindist [] | p::[] = INFINITY
|   mindist p1::p1::[] = dist(P[0], P[1])
|   mindist p::r = let m = mindist(r) in
                     min(m, nextNeighbour(p, r, m))
                   end

Zauważ, że jest (osiągając) w czasie liniowym, ponieważ tylko liczba stała punktów rmoże być farer z dala od mz p(zakładając, że powyższe oświadczenie); tylko te punkty muszą zostać zbadane w celu znalezienia nowego minimum. Oczywiście jest pewien haczyk; jak wdrażasz nextNeighbour(być może z przetwarzaniem wstępnym w czasie liniowym)?

Pytanie 2 : Niech zbiór punktów i punkt . Niech przy pomocyp ∉ R m ∈ $R$$p \notin R$$m \in \mathbb{R}$

$\qquad m \leq \min\{\mathrm{dist}(p_1, p_2) \mid p_1, p_2 \in R\}$

i

$\qquad R_{p,m} := \{p' \mid p' \in R \wedge \mathrm{dist}(p, p') \leq m\}$ .

Załóżmy, że jest skończony. Czy można znaleźć przy minimalnej odległości od w (zamortyzowanym) czasie ? (Możesz założyć, że jest konstruowane przez dodawanie badanych punktów jeden po drugim.)$R_{p,m}$$p' \in R_{p,m}$$p$$\mathcal{O}(1)$$R$$p$

Nie można rozwiązać problemu w czasie krótszym niż w standardowych modelach, np. Przy użyciu drzew decyzyjnych algebraicznych. Wynika to z pracy Yao i Ben-Or, która pokazuje, że w tym modelu nie można zdecydować, czy zbiór liczb wejściowych jest inny, czy nie (patrz http://people.bath.ac.uk/masnnv /Teaching/AAlg11_8.pdf ). W przypadku problemu wyobraź sobie, że wszystkie znajdują się na linii rzeczywistej. Jeśli dwa punkty są takie same, wynik będzie równy dwóm punktom z odległością zero, podczas gdy w przeciwnym razie nie, więc rozwiązanie problemu rozwiązałoby również problem LICZBY ODLEGŁYCH. Jeśli chcesz założyć, że wszystkie twoje punkty są różne, po prostu dodaj do$cn\log n$$n$$i\epsilon$$x_i$dane wejściowe problemu DISTINCT NUMBERS, w tym przypadku, jeśli twój wynik wynosi co najwyżej , wówczas liczby nie są różne. (Chociaż w tym przypadku musisz użyć obiecanej wersji, w której różnica dowolnych dwóch odrębnych liczb wynosi co najmniej , ale myślę, że ten sam dowód działa, aby pokazać, że potrzebujesz również w tym walizka.)$n\epsilon$$2n\epsilon$$\Omega(n\log n)$

Istnieje losowy algorytm liniowego oczekiwanego czasu według Rabina; patrz np. Rabin Flips a Coin na blogu Lipton.

O ile rozumiem pytanie 2, algorytm Rabina również stanowi na to odpowiedź. Na każdym etapie struktura danych jest siatką o szerokości komórki mniejszej niż najmniejsza dotychczasowa odległość między parami punktów, podzielona przez (tak, że żadna komórka nie zawiera więcej niż jednego punktu). Aby odpowiedzieć na pytanie w pytaniu 2, wystarczy zmapować do komórki w siatce i spojrzeć na stałą liczbę komórek wokół niej. Dzięki analizie algorytmu, jeśli zestaw punktów wejściowych jest badany w kolejności losowej, wówczas zamortyzowany czas aktualizacji dla siatki wynosi na oczekiwany nowy punkt.$\sqrt{2}$$p$$O(1)$