Limites de trocas para a contagem de intervalo de meio espaço

10

Qual é o melhor limite atual para a execução de consultas de contagem de intervalo no meio-espaço em um conjunto de pontos bidimensionais , expressos na forma de uma troca de tempo / espaço. De acordo com o artigo seminal de Matousek, de 1993 (Teorema 6.2, Pesquisa por Gama com Cortes Hierárquicos Eficientes), podemos fazer contagens de alcance para consultas que são a interseção de semi-espaços , para , usando uma estrutura de dados de tamanho , para , em $d$ $p$ $1 \le p \le d+1$ $O(m)$ $n \le m \le n^d$ tempo. Paraeste é o tempo. No entanto, a pesquisa da Agarwal sobre pesquisa por alcance (Tabela 36.3.2) afirma que o limite é $O\left(\frac{n}{m^{1/d}}\log^{p-(d-p+1)/d} \left(\frac{m}{n}\right)\right)$ $p=1$ $O(n/m^{1/d})$ . Qual é a afirmação correta do limite? Como alternativa, o que estou entendendo mal? Finalmente, existe algum termo de log oculto quando? $O\left(\frac{n}{m^{1/d}}\log(\frac{m}{n})\right)$ $m=n^d$

reference-request ds.data-structures cg.comp-geom pkn
fonte

6

O tempo mais forte de Matoušek está correto.

A prova do Teorema 6.1 ( na versão do diário ) usa um truque indireto que reduz o limite de espaço necessário para o tempo de consulta logarítmica de para . Intuitivamente, o truque é agrupar os pontos em subconjuntos de tamanho polilogarítmico, criar uma estrutura de dados de espaço linear para cada subconjunto e depois construir uma estrutura padrão de tempo de consulta logarítmica nos subconjuntos. Conectando o espaço aprimorado vinculado à maquinaria de vários níveis / troca de Matoušek - descrita em generalidade sangrenta na versão mais longa da pesquisa de Agarwal $O(n^d)$ $O(n^d/\operatorname{polylog} n)$ - fornece a forma de troca de espaço-tempo de Matoušek. (Na verdade, o truque de indireção é apenas uma aplicação muito cuidadosa do mecanismo de troca padrão.)

Jeffε
fonte

Apenas para ser explícito: o teorema 6.2 do artigo de Matousek afirma que a contagem de meio espaço pode ser feita no espaço

, tempo

. Quando

, esse é o tempo

... não há fator de log aditivo não declarado? Só pergunto porque, na pesquisa, o Teorema 7 e o Corolário 8 têm um aditivo

que não está presente na declaração do teorema de Matousek.

O (m)

$O(m)$

O (n / m^{1 / d})

$O(n/m^{1/d})$

m = n^{d}

$m = n^d$

O (1)

$O(1)$

O (l o g (m / n))

$O(log (m/n))$

pkn

Ah entendo. Sim, há um bug; o limite superior

na declaração do teorema é muito frouxo. A prova requer

; caso contrário, o parâmetro inteiro

seria menor que

. Adicionar o termo logairthmic ao tempo da consulta também corrige o problema.

m \leq n^{d}

$m \le n^d$

m = O (n^{d} / \log^{d - p + 1} n)

$m = O(n^d / \log^{d-p+1} n)$

r

$r$

1

$1$

Jeffε

2

Há uma breve discussão dos resultados na busca por meio espaço, logo acima da Tabela 36.3.2 na Pesquisa da Agarwal e outra na seção 4.3 desta pesquisa . O primeiro parece não fornecer muitos detalhes além de "É possível obter uma troca de espaço / tempo de consulta para pesquisa de intervalo simplex combinando as estruturas de dados de tamanho linear e logarítmico de tempo de consulta", mas o último parece fornecer um pouco mais detalhes sobre a troca de espaço / tempo de consulta. Sugiro olhar para a seção 4.3, Teorema 7, Corolário 8, e suas provas. Não os li com detalhes suficientes para saber se responde totalmente à sua pergunta, mas é pelo menos um bom ponto de partida.

Joe
fonte

Limites de trocas para a contagem de intervalo de meio espaço

Respostas: