[Prévia] [Próxima] [Prévia por assunto] [Próxima por assunto]
[Índice cronológico]
[Índice de assunto]
RE: Problema do numero de pontos
- Subject: RE: Problema do numero de pontos
- From: Yoshiharu Kohayakawa <yoshi@ime.usp.br>
- Date: Fri, 26 Mar 1999 12:51:14 -0300
Lennon Machado writes:
> Prof. Yoshi e colegas,
>
> Estive pensando no problema discutido ontem (25/3/99) e acho que uma
> solucao um pouco melhor seria fazer uma grade com passo igual a d sobre
> raiz de 2 (com d<1), criando quadrados com a diagonal igual a d, e
> garantindo que todos os pontos que estiverem dentro do quadrado, com
> certeza estarao a uma distancia menor ou igual a d; desta forma nao
> seria necessario computar o quadrado central,
----------
| | | |
----------
| | x| |y
----------
| | | |
----------
Nao seria possivel o ponto x (bem perto da aresta direita do quadrado central)
e o ponto y (bem perto da aresta esquerda do quadrado lateral, nao um dos 9)
estarem a distancia menor que d? Acho que sim... Mas pode ser que o uso de
uma figura mais proxima de um disco (e nao um quadrado) em torno de cada
quadrado d x d leve a um aumento de eficiencia (imagino que poderia se fazer
isto com uma grade bem fina, e o uso de uma configuracao diferente de um
quadrado 3 x 3). Precisaria ver uns detalhes (para ver se vale a pena)...
Boa sorte a todos!!! Yoshi
> restando apenas saber a
> quantidade de pontos existentes dentro deste quadrado (facilmente
> conseguido com uma cabeca de lista). Assim:
>
> -P/ grade = d:
> Area = 9*d^2
> Numero de pontos = N*9*d^2
> Numero de distancias = 9^2 * d^4 * N^2 / 2
> Para todos os quadrados (* 1/d^2): 40.5 * d^2 * N^2
>
> -P/ grade = d / raiz(2):
> Area = (9 * d^2 / 2 ) - (d^2 / 2) = 4*d^2
> Numero de pontos = N*4*d^2
> Numero de distancias = (4^2 / 2) * d^4 * N^2 = 8 * d^4 * N^2
> Para todos os quadrados (* 2/d^2): 16 * d^2 * N^2
>
> Uma economia de tempo (teoricamente) com fator de 2.53125.
>
> Esta correta esta elucubracao ?
>
> Lennon Machado
> 26/3/99 8h20min
>
>
>
> Get Your Private, Free Email at http://www.hotmail.com