RE: Re: Dúvida sobre fase de COMBINAR

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

Paulo Eduardo Azevedo Silveira writes:
 > pensei tanto nesse exercico que ja nao sei mais nada, tipo, me perdi, sabe
 > qdo acontece isso?
 > 
 >                   |
 >                   |
 >       5PL--------6PL----------7PR
 >       |           |            |
 >       |           |            |
 >       |           |            |
 >       |          4PR           |
 >       |           |            |
 >       |           |            |
 >       2PL--------1PL----------3PR
 >                   |
 >                   |
 >         "reta do ponto-mediana"
 > 
 > pontos a esquerda(e nela) do ponto- mediana: 1PL, 2PL, 5PL, 6PL
 > ponto a direita do ponto-mediana: 3PR, 4PR, 7PR

Puxa, que bacana. Deve ter dado um trabalhão fazer o desenho 

 > 
 > os numeros indicam a ordenacao Y deles.
 > vamos analisar o caso de verificacao do ponto 1PL
 > 

Perfeito.

 > Voce pode ver que esse caso pode existir, pois nenhum par de  pontos em L
 > dista menos que DEL, e nenhum par de pontos em R dista menos que del
 > 

É verdade.

 > sendo que DEl = min (delL, delR) {como visto em aula)
 > 
 > 1PL e 4PR distam menos que DEL, porem eles estao em lados diferentes do
 > ponto mediana.
 > 
 > tipo
 > eh necessario verificar a distancia do 1PL com todos os outros pontos
 > desse retangulo?

Acho que não, basta para em 4PR. A numeração que você colocou sugeri isto.

 > creio que sim, mas ainda nao encontrei a explicacao, pois o 7PR eh o
 > ultimo na ordenacao e com certeza nao dista menos de DEL de 1pl
 > mas eh por ai o raciocinio
 > acho que so embaralhei mais.

Acho que não embaralhou não. A sua análise e exemplo estão muito bons. Você
mostrou que é possível colocar 7 pontos no retângulo sem violar a restrição de 
dois-estão-mais-próximo-que-delta. Por outro lado, apesar de muito bacana, o
exemplo não mostra que é _necessário_ examinar/verificar as distâncias entre cada
ponto p em P^* e os 6 pontos que seguem p na lista P^*. Me parece que o
exemplo mostra que é necessário verificar a distância entre p e 3 pontos 
(as disntâncias entre 1PL e 2PL, 3PR e 4PR).

inté +,
coelho