Discussion :

[biba1980]

Bonjour,
Il s'agit de trouver les deux points les plus proches dans un plan par un algorithme de type diviser pour reigner.
J'ai éssayé de construire deux tableau un pour les abssisse et un pour les ordonées X et Y, les trier et diviser le X en deux (parties des points gauches et une autre partie droite). Trouver les points les plus proches de chacune des parties.
Mais si la dimension du plan est en 3D, donc 3 coordonées pour chaque point, on aura 3 tableaus X, Y et Z. Si je dois diviser, je divise selon les X et Z ou seulement selon les X ? À votre avis ?
Merci pour votre aide.

[Graffito]

Pour rester dans les généralités, diviser en 2 est insuffisant.
Il faut diviser en 3 intervalles au minimum : notons ces intervalles [AB], [BC] et [CD].
Ainsi, quelque soit le point P1 appartenant à [AB] et quelque soit P2 appartenant à [CD], alors Dist(P1,P2) sera supérieure à Dist(B,C).

[biba1980]

j'avoue que je n'ai pas très bien compris, comment ça diviser en 3. est ce qu'on divise par 3 lorsuqe les points sont en 3 dimensions?

[Graffito]

3 c'est juste le minimum sur une des dimensions pour pouvoir optimiser le minimum de la distance entre 2 groupes de points. Car, si on considère 2 groupes adjacents, il pourra y avoir des points très proches de part et d'autre de la frontière.

L'idée est donc en 1 D de diviser en intervalles, en 2D en carrés, en 3D en cubes.

[biba1980]

Je suis désolée mais c'est encore pas compris. Je divise en deux, je cherche le minimum des distances. par exemple, je divise en Xdroite et Xgauche. Je cherche la dictance min1 dans Xdroite, puis la dictance min2 dans Xgauche, et la le min sera le minimum des (min1,min2).

[Graffito]

Je cherche la dictance min1 dans Xdroite, puis la dictance min2 dans Xgauche, et la le min sera le minimum des (min1,min2).

ça ne suffit pas : il peut y avoir un point A à droite et un point B à gauche tels que dist(A,B)<minimum des (min1,min2).

[pseudocode]

Pour rester dans les généralités, diviser en 2 est insuffisant.
Il faut diviser en 3 intervalles au minimum : notons ces intervalles [AB], [BC] et [CD].
Ainsi, quelque soit le point P1 appartenant à A et quelque soit P2 appartenant à B, alors Dist(P1,P2) sera supérieure à Dist(B,C).

C'est l'algo de Bentley and Shamos (cf. leur publication "Divide-and-conquer in multidimensional space")

[biba1980]

Je suis desolée, je n'ai pas vu vos réponses, j'étais sur un autre devoir.
Je vais jetté un coup d'oeil sur l'article, merci.

[biba1980]

ça ne suffit pas : il peut y avoir un point A à droite et un point B à gauche tels que dist(A,B)<minimum des (min1,min2).

Je sais Graffito qu'il faut prendre en considération ce point, mais pour mettre en place un algorithme, c vraiment dur.