RE: Problema do numero de pontos

["Lennon Machado" <lennonx@hotmail.com>]

>From: Yoshiharu Kohayakawa <yoshi@ime.usp.br>
>To: "Lennon Machado" <lennonx@hotmail.com>
>CC: yoshi-mac324@ime.usp.br
>Subject: RE: Problema do numero de pontos
>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...  

Realmente, me esqueci deste detalhe, minha preocupacao era que duas 
arestas somassem mais do que d (d/raiz(2)+d/raiz(2)=d*raiz(2) > d), 
porem com os pontos proximos as arestas isso nao funciona, pois a 
distancia entre eles eh de aproximadamente d/raiz(2) o que eh menor que 
d.

Lennon Machado
30/3/99 6h50min

>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

Get Your Private, Free Email at http://www.hotmail.com