Re: Dúvida sobre fase de COMBINAR

[Paulo Eduardo Azevedo Silveira <peas@linux.ime.usp.br>]

Oi Livio

1-)
sobre a 1, eh o seguinte, voce pega o ponto que voce considera a mediana e
manda metade pra um lado (contendo o ponto da mediana) e metade pro outro

Vamos super que temos as seguintes X coordenadas dos pontos

1    5    5    5    10
          ^

Ja que ordenamos e pegamos o ponto para ser da linha mediana, pegamos esse
5 bem do meio, entao, a galera da esquerda pra la contado com ele eh L, e
da direita eh R

nota que assim teremos 3 pontos na mediana, 2 em L, 1 em R
Se voce tivesse adicionado mais um 5, poderia estar proximo de cair
naquele pior caso, que eh ter 4 pontos na mediana.

2-)
da 2, eh que voce pode ter a seguinte distribuicao que o professor Maqui
Esperto nao pensou

PL         PL           PR
           |            
           |
           |
           PR
           |
           |
PL         PL           PR
           |
         "mediana"

isso eh, teremos no total 6 pontos para comparar
PR - ponto do lado direito
PL - ponto do lado esquerdo.

Eh muito comum a gente se enganar como o Maqui Esperto e pensar que o pior
caso eh:


PL         PL           PR
           |            
           |
           |
           |
           |
           |
PL         PL           PR
           |
         "mediana"

Porem podemos ter outro PR em cima da mediana.
Paulo


Paulo Eduardo A. Silveira   <peas@linux.ime.usp.br>
UIN: 5142673   www.paulo.com.br

On Tue, 3 Apr 2001, Livio Baldini Soares wrote:

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