RE: Dúvida sobre fase de COMBINAR

[Jose Coelho de Pina <coelho@ime.usp.br>]

Talvez alguém já tenha respondido, mas aqui vai.

Livio Baldini Soares writes:
 > Pergunta 1
 > ----------
 > 
 > Não estou conseguindo saber se os pontos que estão sobre a reta $l$
 > pertencem à $P_{L}$ ou (exclusivamente) à $P_{R}$ ou à ambos $P_{R}$ e
 > $P_{L}$. Primeiro pensei esses pontos (de $l$) pertencessem a ambos os
 > lados, lendo a frase:
 > 
 > "... seja $l$ uma reta tal que todo ponto de $P_{L}$ está a esquerda
 > ou sobre $l$ e todo ponto de $P_{R}$ está a direita ou sobre $l$."
 > 
 > Mas vendo a análise na apostila:
 > 
 >             { $D(round_down(n/2))$ + $D(round_up(n/2))$ + cn
 > $D(n)$ <=   {
 >             { a
 > 
 >   Aqui parece que os pontos de $l$ estão em apenas um dos lados, caso
 > contrário, a análise seria $2 \times D(round_up(n/2)) + cn$, não?

Nós ordenamos os pontos em um vetor de acordo com as x-coordenadas. Digamos
que os pontos já ordenados são 

      p_1, p_2, p_3, ..., p_n

Agora nos quebramos este vetor em duas partes 

P_l = p_1,p_2,...,p_{chão{n/2}}
P_l = p_{chão{n/2}+1}, p_{chão{n/2}+2}, ..., p_n


Desta forma os pontos que estão em P_L estão à esquerda ou sobre a reta
vertica passando por p_{chão{n/2}} e P_R estão à direita ou sobre a reta 
passando por p_{chão{n/2}}. Considere o seguinte exemplo para n=3

 p_1=(1,2)  p_2=(1,3) e p_3=(1,1)

Note que os pontos estão ordenados de acordo com a x-coordenada. Neste caso 
P_L = {p_1} e P_R={p_2,p_3}. Tanto P_L como P_R tem pontos sobre a reta x=1.


 > 
 > Pergunta 2
 > ----------
 > 
 >   Outra questão mais ou menos relacionada com a acima, é sobre o
 > exercício 6 da lista 1. Por que não é suficiente verificar somente 5
 > pontos que seguem cada ponto em $P^{*}$? 

Eu não sei. Na realidade acho que é suficiente verificar 5. (Se não me engano
eu tenho um exemplo que mostra que com 4 não dá, ou que é com 3...)

 > Anteriormente parece que
 > seria necessário verificar 7 desses pontos devido aos pontos
 > coincidentes que estariam em $l$, 

Os argumento apresentados mostraram que são _suficientes_ 7, mas não que são
_necessários_ 7. Como você observou dá para fazer com menos.

 > mas como tiramos essa redudância
 > fazendo com os pontos em $l$ pertençam somente a um dos lados, então
 > parece que dois dos possíveis pontos serão eliminados, assim sobrando
 > 5 dos 7 pontos.

Existem duas questões sobre este negocio de verificar x pontos. Uma coisa é
mostra que é suficiente verificar x pontos. Para isto `basta' mostra que no
retângulo de lados delta x 2 delta, sob determinadas condições, não cabem mais
do que x (ou x+1) pontos. Outra coisa é mostrar que é necessári examinar os
tais x pontos, para isto devemos mostrar um exemplo em que o algoritmo, por
deixar de verificar o x-ésimo pontos, responde uma bobagem.

Legal esta coisas não ;-)


coelho