RE: Problema do numero de pontos

[Yoshiharu Kohayakawa <yoshi@ime.usp.br>]

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