Apresenta O

Simplex Range Searching

Por Jorge Rama e Carlos Siestrup

Simplex Range Searching
●

●

Dado um conjunto P de n pontos no R² e dado uma “query” em uma região , os pontos P   podem ser contados e informados eficientementes. Assumindo que a região é um polígono simples, se não for , podemos utilizar a triangulação. Exemplo de query “Half Plane”

Resolvendo usando Árvores de partição (partition trees)

Particionando os conjuntos de pontos ●

Agrupar os pontos em triângulos ( que não precisam ser disjuntos) , assim criamos uma partição simplicial.

Partição Simplicial
●

●

Nós dizemos que a linha H corta um triangulo quando passa pelo seu interior. No exemplo decima o número de cortes é 2.
Com esses triangulos a busca na arvore de partição fica muito mais eficiente

Aplicação

Ordem
●

Triangular os pontos : nlogn

●

A ordem fica em : O(n^(1/2)+ε)

Árvores de partição multi-níveis
●

A idéia é guardar dentro de cada nó, não somente um número, mas outra estrutura de dados. Árvores de partição multi-níveis
●

Exemplo: Queremos contar o número de segmentos que cruzam a linha “query” L, vamos dizer que pright(s) e pleft(s).

Árvores de partição multi-níveis
●

●

●

Primeiro achamos todos os segmentos pright que estão acima da linha l .
Para cada subset canônico gerado, nós queremos aqueles que possui o pleft abaixo da linha l
Isso é uma query de contagem half-plane que pode ser resolvida se guardarmos o subset em cada nó da árvore

Ávores de partição multi-níveis
●

●

O set pright(S) é guardado na árvore de partição T.
O subset canônico de nó v do T vai ser denominado
Pright(V). O set de segmentos correspondentes ao pontos finais do pright(v) são chamaods S(V)
Para cada nó v no primeiro nível da árvore T, nós guardamos o pleft(S(v)) no segundo nível da árvore de partição T assoc para a contagem de half-plane.
Essa árvore de partição é associada a estrutura v;

Ordem
●

●

A ordem de espaço na memória de uma árvore de 2 níveis é O(nlogn)
O número de