Encontre a menor distância par a par de pontos em o (n log n)?

O exercício a seguir foi entregue aos alunos que eu supervisiono:

Dados $n$ pontos no plano, crie um algoritmo que encontre um par de pontos cuja distância seja mínima entre todos os pares de pontos. O algoritmo deve ser executado no tempo $o(n^2)$ .

Existe um algoritmo de divisão e conquista (relativamente) simples que resolve a tarefa no tempo $\Theta(n \log n)$ .

Pergunta 1 : Existe um algoritmo que resolve o problema em questão exatamente na pior das hipóteses, $\mathcal{o}(n \log n)$ ?

O que me fez suspeitar que isso seja possível é um resultado que lembro de ter visto em alguma conversa (referência apreciada). Ele afirmou algo ao longo das linhas que não mais do que um número constante $c \in \mathbb{N}$ de pontos pode ser arranjado no plano em torno de algum ponto $p$ dentro de um círculo de raio $r \in \mathbb{R}$ , com $r$ a distância mínima entre dois dos pontos envolvidos . Eu acho que $c=7$ , os pontos formando um hexágono equilateral com $p$ no centro (no caso extremo).

Nesse caso, o algoritmo a seguir deve resolvê-los em $n$ etapas.

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

Note que este é (alegou ser) em tempo linear, pois apenas um número constante de pontos rpode haver farer longe do que ma partir de p(assumindo acima declaração); somente esses pontos precisam ser investigados para encontrar um novo mínimo. Há uma pegadinha, é claro; como você implementa nextNeighbour(talvez com pré-processamento em tempo linear)?

Pergunta 2 : Deixe um conjunto de pontos e um ponto p ∉ R . Seja m ∈ R com$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\}$

e

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

Suponha que seja finito. É possível encontrar com distância mínima de em tempo (amortizado) ? (Você pode supor que seja construído adicionando pontos investigados um por um.) p ' ∈ R p , m p ó ( 1 ) R $R_{p,m}$$p' \in R_{p,m}$$p$$\mathcal{O}(1)$$R$$p$

É impossível resolver o problema em menos de tempo em modelos padrão, por exemplo, usando árvores de decisão algébricas. Isso se segue do trabalho de Yao e Ben-Or, que mostra que, neste modelo, não é possível decidir se um conjunto de números de entrada é diferente ou não (consulte http://people.bath.ac.uk/masnnv /Eaching/AAlg11_8.pdf ). No caso de seu problema, imagine que todos eles estejam na linha real. Se dois pontos forem iguais, sua saída será de dois pontos com distância zero, caso contrário não, portanto, uma solução para o seu problema também resolveria o problema DISTINCT NUMBERS. Se você quiser supor que todos os seus pontos são diferentes, basta adicionar aon i ε x i n ε 2 n ε ohms ( N log N $cn\log n$$n$$i\epsilon$$x_i$entradas do problema DISTINCT NUMBERS, neste caso, se sua saída for no máximo , os números não serão todos distintos. (Embora, neste caso, você precise usar uma versão de promessa em que a diferença de dois números distintos seja pelo menos , mas acho que a mesma prova funciona para mostrar que você também precisa de neste caso.)$n\epsilon$$2n\epsilon$$\Omega(n\log n)$

Existe um algoritmo linear aleatório de tempo esperado por Rabin; veja, por exemplo, Rabin lança uma moeda no blog de Lipton.

Por mais que eu entenda a pergunta 2, o algoritmo de Rabin fornece uma espécie de resposta para isso também. Em cada etapa do tempo, a estrutura de dados é uma grade com largura de célula menor que a menor distância entre pares de pontos vistos até agora, dividida por (para que nenhuma célula contenha mais que um único ponto). Para responder à consulta na pergunta 2, você só precisa mapear para uma célula na grade e observar um número constante de células ao seu redor. Pela análise do algoritmo, se o conjunto de pontos de entrada for examinado em ordem aleatória, o tempo de atualização amortizado para a grade será por novo ponto na expectativa. pO(1$\sqrt{2}$$p$$O(1)$