RE: EP3 - é melhor buscar outro algoritmo?

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

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.)

 >     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ê