Dúvida sobre fase de COMBINAR

[Livio Baldini Soares <livio@linux.ime.usp.br>]

  Olá pessoal,

  estou aqui estudando e tentando resolver os exercícios com relação à
fase de COMBINAR do algoritmo de divisão-e-conquista para calcular o
par-mail-próximo no plano. Estou com algumas dúvidas...

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?

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^{*}$? Anteriormente parece que
seria necessário verificar 7 desses pontos devido aos pontos
coincidentes que estariam em $l$, 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.
  
  Falous!

--  
  Livio <livio@linux.ime.usp.br>