[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: "Lennon Machado" <lennonx@hotmail.com>
- Date: Tue, 30 Mar 1999 01:50:46 PST
>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