RE: EP3 - é melhor buscar outro algoritmo?

[Leonardo Giantini Trabuco <ltrabuco@cecm.usp.br>]

On Sat, 15 Jun 2002, Yoshiharu Kohayakawa wrote:

> Sinuê Dayan Barbero Lodovici wrote (on Saturday, 15 Jun 2002, at 14:54:31 -0300):
>  > Olá, Professor! Oi, pessoal!
>  >     Professor, minha dúvida quanto ao EP3 é a seguinte... Meu algoritmo é
>  >     igual ao do Leo: 
>  >     Montando a árvore:
>  >         Chegando num nó externo, substituo o mesmo por uma árvore com um nó
>  >         interno (com a reta adicionada) e dois externos.  Para adicionar
>  >         uma reta faço o seguinte: comparo a reta sendo a dicionada com a do
>  >         1º nó da árvore. Se forem concorrentes adiciono nas duas
>  >         sub-árvores, caso contrário apenas em uma sub-árvore de acordo com
>  >         a posição relativa das retas.  Isso é feito recursivamente...
>  > 
>  >     Bom o problema é uso excessivo de memória...
>  >     O uso excessivo da memoria é esperado! Imagine que todas as retas são
>  >     duas a duas concorrentes entre si. O q aconteceria: 2 nós seriam
>  >     criados para cada nó externo a cada adição de uma reta (pois sempre
>  >     mandariamos as retas para ambos os lados em cada nó interno)! O uso de
>  >     memória cresce exponencialmente! 
>  > 
>  >     Minha pergunta é: Vale a pena tentar ordenar as retas para conseguir
>  >     adicioná-las numa ordem ótima? Ou é melhor buscar um algoritmo melhor?
>  >     Observe que o exemplo acima tornaria inútil buscar uma ordem melhor
>  >     (inexistente)...
> 
> O Leo e voce estão tendo o mesmo problema com esse algoritmo.  Usarei o seu
> diagrama para explicar o que acho que deve ser feito.
> 
> A árvore nao deve conter o nó 3 abaixo do qual voce tem aquele nó ??.  De
> fato, note que aquele nó "nao serve para nada".  De fato, voce pode associar o
> filho esquerdo de 2 (que deve ser um nó externo) com a regiao G.  Dessa forma
> voce terá um nó externo para cada regiao e assim serao "poucas", de forma que
> a árvore também será pequena.
> 
> O seu algoritmo deve ser melhorado para nao inserir aquele nó 3.
> Geometricamente, por que aquele nó não é necessário?  Fácil: a reta 3 não
> corta a regiao G em duas!  (Em termos de programacao, voce terá de pensar como
> implementar isso.)

Sinuê, de fato estamos fazendo o seguinte: em um nó genérico, se a reta
que estamos tentando inserir intersecta a reta do nó no quadrado (0,1),
inserimos dos dois lados. Falta fazer um teste para ver se a intersecção
ocorre em uma região "possível". No seu desenho, abaxo de 1 e à esquerda
de 2, já está determinada a região G. A reta 3 nunca poderia ser inserida
dos dois lados de 2... tenho que pensar como fazer isso...

Até mais,
Leo.

> 
>  >     Obrigado, (Estou mandando para todos atravé da lista do CCM. Não
>  >     consegui entrar na lista de Computação e acho que nem vale a pena
>  >     entrar agora (a não ser que a lista continue existindo após o fim das
>  >     aulas
> 
> Pretendo manter a lista enquanto der.  Assim, estou enviando esta mensagem
> para lá tambem.  Boa sorte!  Yoshi
> 
>  >          ))
>  >     
>  >         Sinuê
>