Discussion :

[Trap D]

Bonjour

Je me posais une question toute bête, je connais la notion du barycentre de points du plan, je sais calculer ses coordonnées, mais existe-t-il un point inverse du barycentre, c'est-à-dire un point qui, dans une région donnée serait le plus éloigné possible de tous les points ???
Peut-être que la réponse est évidente et que pour une raison ou une autre elle m'échappe ?
En tout cas pouvez-vous me donner des pistes de recherches sur cette notion ?
Merci

[tbc92]

D'un point de vue mathématique, le point en question n'a pas de nom particulier, et il n'y a pas de technique immédiate pour le trouver.

Si tu as besoin de ce point, tu vas devoir d'abord chercher le barycentre B.
Puis à partir de ce point B, il va falloir que tu cherches le point le plus éloigné de B dans la région que tu t'es fixée. Si la région est un disque, ça va être facile ; Mais dans le cas général, ça peut être complexe.

[Trap D]

Pas bête du tout comme idée . Merci, je vais creuser.

[Vincent PETIT]

Je vais peut être dire connerie sans nom mais si tu calculais un écart type ? D'habitude on calcule l'écart type (dispersion) par rapport à une moyenne mais on ne pourrait pas le faire par rapport à un barycentre (qui est une moyenne pondérée si je ne m'abuse) ????

[pseudocode]

Si tu as besoin de ce point, tu vas devoir d'abord chercher le barycentre B.
Puis à partir de ce point B, il va falloir que tu cherches le point le plus éloigné de B dans la région que tu t'es fixée.

Heu... si on prend les 4 coins d'une région carrée, j'ai comme dans l'idée que le point le plus éloigné des 4 coins... c'est justement le barycentre.

On peut trouver ce point avec un diagramme de Voronoï ou, si c'est un espace discret (bitmap ?) avec une carte des distances.

Je ne crois pas qu'il existe de nom pour ce point, à part "point le plus loin" (farthest point).

[Trap D]

Merci pseudocode !
On trouve des liens avec farthest point sur Google. Reste plus qu'à regarder de près.
Ça me rassure un peu, je n'ai pas posé une question complètement stupide

[tbc92]

Effectivement, j'ai peut-être mal compris la question.

Quand tu dis que tu recherches : Dans une région donnée, le point le plus éloigné possible de tous les points ... ça veut dire quoi ?

Tu as n Points ( A1 ... An)
Tu cherche un 'farther point' F

Et la fonction que tu cherches à maximiser, c'est laquelle :
- la somme des distances entre F et chacun des points Ai
- le distance maximale parmi les distances d(Ai,F)
- le distance minimale parmi les distances d(Ai,F)

Dans cette 3ème option, on est dans le cas donné par Pseudocode, et effectivement sur un carré, le "Farther point" se trouve être aussi le barycentre.

[wiwaxia]

Bonjour,

Ta question, nullement stupide, déroute en raison des ambiguïtés de sa formulation:

... mais existe-t-il un point inverse du barycentre, c'est-à-dire un point ... qui, dans une région donnée serait le plus éloigné possible de tous les points ?

1°) Contrairement à la notion de barycentre, la question n'a de sens que sur une domaine borné, d'extension finie - qu'il s'agisse d'une courbe, d'une surface ou d'un volume; sinon, en l'absence de définition de ce domaine, il n'y a pas de réponse et l'on est conduit à rechercher une solution qui n'existe pas ... et à des contradictions:

... si on prend les 4 coins d'une région carrée, j'ai comme dans l'idée que le point le plus éloigné des 4 coins... c'est justement le barycentre.

D'autres ont pressenti le lien entre l'existence de la solution et la délimitation de la région à laquelle on lui impose d'appartenir.

... il va falloir que tu cherches le point le plus éloigné ... dans la région que tu t'es fixée. Si la région est un disque, ça va être facile ; mais dans le cas général, ça peut être complexe.

Donc pour être clair, c'est le titre même de ta question qui laisse les intervenants perplexes, et qu'il faudrait changer ( le titre, pas les intervenants).

2°) Encore faut-il définir l'éloignement d'un point donné (P) vis-à-vis d'un ensemble de (N) autres points (M₁, M₂ ... M_N); plusieurs possibilités se présentent.
a) Rechercher la position de (P) la plus éloignée du point (M_i) le plus proche appartenant au nuage : c'est alors un problème de minimax, démarche déjà implicitement suggérée:

... On peut trouver ce point avec un diagramme de Voronoï ...

b) Envisager une simulation physique, où (P) se déplace sous l'action de forces centrales répulsives exercées par les points du nuage, en associant au système l'énergie potentielle: U_P = S_{[k=1 à N]}(U_k) = S_{[k=1 à N]}F(d_k) dans laquelle F(d_k) est une fonction décroissante de la distance d_k = PM_k .
On aura par exemple: F(d_k) = 1/(d_k)^p; le cas (p = 1) correspond à la répulsion coulombienne entre charges de même signe, (p=12) aux répulsions de Van der Waals intervenant entre deux atomes en contact; la limite (p─>Infini) ramène au cas précédent (a).
Par exemple dans un métal de structure cubique à faces centrées, les atomes d'impuretés (C, N, O), plus petits, se logent dans les lacunes octaédriques du réseau, au centre de l'octaèdre formé par les atomes métalliques; c'est un exemple de minimum local d'énergie potentielle, correspondant à l'éloignement maximal vis-à-vis des plus proches atomes voisins, et que pseudocode a vaguement évoqué.

... si on prend les 4 coins d'une région carrée, j'ai comme dans l'idée que le point le plus éloigné des 4 coins... c'est justement le barycentre.

c) Et puisque beaucoup ont parlé du barycentre, on peut rappeler que (G) est la position particulière du point (P) pour laquelle la somme des carrés des distances qui le séparent des (N) points du nuage est minimale; il s'agit donc de l'unique extremum de la fonction (U_P) précédemment décrite, avec (n = -2) ; il ne peut y avoir d'autre point "inverse" du barycentre, ou "contraire" à celui-ci.

Je viens de découvrir la dernière intervention de tbc92, dont les remarques vont dans le même sens

[Trap D]

Merci de vos interventions.

Je rappelle mon problème. j'ai une distribution (D) de points répartis dans une région (R), par exemple un rectangle.
Je sais calculer l'iso barycentre des points de (D) (donc la région ici n'a aucune importance), ce barycentre minimise, si je ne me trompe pas, la moyenne des distances entre ce point et les point de (D).
Je me pose la question, " Existe-t-il un point de (R) qui maximise cette moyenne des distances ?" C'est plus précis effectivement que point le plus éloigné des points de (D).
Si j'ai bien compris le post de wiwaxia, ce point n'existe pas (alinéa c de l'intervention, moi je parle de moyenne des distances et wiwaxia de somme de carres des distances, j'avoue que je ne sais pas si la différence d'expression entaîne de grandes différences dans le résultat).

Il me parait évident que si par exemple :
- la région est un rectangle
- les points sont répartis dans le sous-rectangle inférieur gauche,
le point que je rercherche est le coin supérieur droit.

Le problème est plus difficile (et n'a peut-être pas de solution) si les points sont répartis sur toute la surface du rectangle, le rectangle pourrait alors être considéré comme "l'enveloppe des points" ? Les diagrammes de Voronoi sont peut-être une piste vers la solution ?

Je reste perplexe.

[tbc92]

Tu veux maximiser la moyenne des distance... on va maximiser la somme des distances. C'est strictement pareil, on a juste une division en moins.
Wixavia parlait de maximiser la somme des carrés des distances, l'avantage de travailler avec les carrés des distances, c'est qu'on arrive a des systèmes d'équations très faciles à résoudre. .. Très facile à résoudre quand on recherche des minimum, mais pas quand on recherche un maximum

Si ta région est un polygone (quelconque), le point recherché est un des sommets. Je n'ai pas la démonstration, mais j'en suis sûr à 99.99%.

Il suffit donc de faire quelques calculs pour savoir lequel des sommets est le 'farther point'.

[dourouc05]

Le problème est plus difficile (et n'a peut-être pas de solution) si les points sont répartis sur toute la surface du rectangle

Je ne vois pas en quoi il n'y aurait pas de solution… En fait, juste pour formaliser encore un peu, tu cherches la solution à ce problème d'optimisation ( étant ton rectangle… ou toute autre zone dans laquelle tu cherches ton maximum) :



(Avec une norme euclidienne, peut se réécrire comme un produit scalaire : . C'est souvent pour ça qu'on met un carré : sans lui, on se coltine une racine carrée…)

Ça ressemble très franchement à des moindres carrés, sauf que tu cherches ici un maximum (et, niveau calculs, c'est nettement moins bien). Selon les cas (c'est-à-dire les points de ), tu seras dans ou à la frontière, impossible à dire en général de manière simple.

Pour un rectangle bien aligné avec les axes, c'est un problème d'optimisation assez bien étudié, avec des variantes de la plus grande pente, notamment. Par exemple, http://www.ingveh.ulg.ac.be/uploads/..._2012-2013.pdf (algo modifié en page 7). D'autres généralisations traitent des régions définies par des droites (http://www.ingveh.ulg.ac.be/uploads/..._2015-2016.pdf, toujours la même source). Sinon, pour d'autres genres de régions (courbes, notamment), il vaut mieux passer par un solveur plus généraliste, à la IPOPT.

Si ta région est un polygone (quelconque), le point recherché est un des sommets. Je n'ai pas la démonstration, mais j'en suis sûr à 99.99%.

Je ne vois pas en quoi ce serait le cas. Si on reprend un exemple précédent, si tu as un carré et quatre points positionnés exactement sur les coins du carré, le point le plus éloigné des autres (au sens de la formulation indiquée plus haut) correspondra au barycentre de ces points (avec une norme euclidienne)… Avec deux-trois calculs sur un coin de table, en norme 1, par contre, c'est le cas (enfin, le simplexe trouvera une solution optimale sur un des coins du polyèdre, mais dans un espace modifié pour encoder les valeurs absolues de la norme 1).

[tbc92]

Si ma surface est un carré de côté 1,
Je calcule la somme des distances entre un point M est les 4 angles.
Si M est le centre du carré, je trouve f(M) = 4 * racine(2)/2 = 2.8...
Si M est un des angles du carrés, je trouve f(M) = 2+Racine(2) = 3.4...
le 'farthest point' est donc bien un des angles.

[dourouc05]

@tbc92 : en effet, je me suis emmêlé les pinceaux à ce niveau.

[Flodelarab]

Bonjour

Première réaction à chaud:
Un barycentre est une moyenne pondérée.
Quand le poids est positif, on se rapproche du point.
Quand le poids est négatif, on s'éloigne du point.

Le point le plus loin serait donc le barycentre avec des poids négatifs.
Pas étonnant que le barycentre des sommets d'un carré de poids -1 soit le centre du carré.

Existe-t-il un point de (R) qui maximise cette moyenne des distances ?
Amha, on reprend ici le raisonnement qui permet de prouver l'infinité de la quantité de nombres entiers.

Si un point très éloigné du nuage donne une moyenne grande, en prenant un point encore plus éloigné, on aura une moyenne encore plus grande.
Donc le point le plus éloigné est rejeté à l'infini.

Après, si on se limite à une région, le point sera peut-être rejeté sur la frontière, ou pas, mais sans définition claire de la région, on ne peut pas répondre.

[wiwaxia]

... ce barycentre minimise, si je ne me trompe pas, la moyenne des distances entre ce point et les points de (D) ...

Le barycentre minimise la moyenne quadratique des distances du point considéré à ceux du nuage: d_q = (S(d_k²)/N)^1/2
et non la moyenne arithmétique: d_m = (S(d_k)/N) , dont l'expression n'a rien de particulièrement simple et remarquable.

Il suffit pour s'en convaincre de revenir à l'expression détaillée de la somme en question, pour un point quelconque (P):
S_P = S_{[k=1 à N]}(d_k²) , avec - en convenant de noter (.│.) le produit scalaire de deux vecteurs:
d_k² = (PM_k│PM_k) = (PG + GM_k│PG + GM_k) = (PG│PG) + 2*(PG│GM_k) + (GM_k│GM_k) = PG² + GM_k² + 2*(PG│GM_k)
ce qui conduit à l'expression
S_P = N*PG² + S_{[k=1 à N]}(GM_k²) + 2*(PG│S_{[k=1 à N]}(GM_k)) , laquelle se simplifie en raison de la présence d'un vecteur nul;
en effet la position de l'isobarycentre (G) vérifie par définition: S_{[k=1 à N]}(GM_k) = 0
de sorte que l'obtient: S_P = N*PG² + S_{[k=1 à N]}(GM_k²) .

Il vient finalement, en posant d₀ = (S_{[k=1 à N]}(GM_k²)/N)^1/2 (moyenne quadratique des distances séparant les points du nuage de son isobarycentre): d_q² = GP² + d₀² .

Le résultat ne fait que confirmer ce qui avait déjà été dit, à savoir que:
a) sur un domaine illimité, il n'y a qu'un seul extremum tant pour la somme (S_P) que pour la distance moyenne d_q, le minimum observé en (G): d_q = d₀ ;
b) à l'intérieur d'un domaine fermé, on peut trouver pour les deux grandeurs précédentes des maximums dont le nombre et l'emplacement sont liés à la forme et à la disposition des frontières, et non pas d'une manière exclusive au point (G) - bien qu'ils en dépendent.

C'est d'ailleurs bien ce que tu exprimes intuitivement:

Il me parait évident que si par exemple :
- la région est un rectangle
- les points sont répartis dans le sous-rectangle inférieur gauche,
le point que je rercherche est le coin supérieur droit.

en prenant d'ailleurs, pour convaincre, un "trop bon" exemple qui marche quel que soit le mode de calcul adopté.

Ce qui bloque, c'est l'à-priori insconscient qui te fait prendre pour une évidence la définition que tu donne de l'éloignement, à savoir la distance moyenne:
d_m = S_{[k=1 à N]}(d_k)/N ;
Se référer à la somme des distances n'a rien d'illégitime, mais c'est un choix contestable, parce qu'il conduit à des calculs formels inextricables; la seule issue est alors un programme de calcul numérique. Et surtout, les résultats n'ont plus rien à voir avec l'isobarycentre (G)!
Pendant qu'on y est, pourquoi ne pas envisager une moyenne établie sur les puissances p-ièmes des distances, et lancer un programme sur le calcul de d_p = (S(d_k^p)/N)^1/p ? Dès qu'on y réfléchit un peu, le choix le plus simple correspond à n = 2 , tant qu'on reste dans un espace euclidien ...

D'autres intervenants ont abondamment répondu depuis, et j'ai du mal à suivre à cause de la typographie- cela peut expliquer quelques redites ou décalages

[souviron34]

Je me posais une question toute bête, je connais la notion du barycentre de points du plan, je sais calculer ses coordonnées, mais existe-t-il un point inverse du barycentre, c'est-à-dire un point qui, dans une région donnée serait le plus éloigné possible de tous les points ???

Bonjour

Alors j'y vais de mon petit grain de sel... (de poivre..)

Je vois 3 cas de figures suivant la définition qu'on donne :

• Cas 1 : comme on l'a dit ci-dessus, on a juste un ensemble de points et on cherche une solution générale. Autant il est facile de calculer le barycentre, autant la notion de "point le plus éloigné" est absurde, puisque l'infini est la solution.
  
  
• Cas 2 : on a un ensemble de points, et on cherche le point parmi ces points qui serait le plus éloigné de tous les autres. Une solution brute supposerait de calculer toutes les distances 2 à 2, en faire les sommes par point, et trouver celui pour lequel la somme est la plus grande.
  
  
• Cas 3 : on a un ensemble de points dans une région délimitée. On cherche le point de la région le plus éloigné de l'ensemble des points. Dans ce cas, il me semble que on doit calculer la somme des distances pour chaque sommet délimitant la région, et trouver celui dont la somme est la plus grande. , en notant aussi le second en rang On peut alors soit s'arrêter là, soit raffiner par dichotomie entre ces 2 points le long du segment (ou par construction géométrique si on a stocké les "vecteurs" de distance : module et direction de la somme).. **

Non ?




** NB: on pourrait aussi, car la somme des distances ne garantit pas le bon résultat, calculer pour chaque sommet la distance min à laquelle on trouve un point, et choisir alors le point ayant la distance min maximum... Ca me semblerait d'ailleurs être la meilleure solution... L'autre trouverait en gros le point le plus éloigné de la moyenne du nuage..

[Trap D]

Il me semble que si on a une région bien délimitée avec une frontière, effectivement on parcourt tous les points de la frontiere et on trouve le maximum.
Moi, ce qui m'intéressait juste c'est savoir si cette notion portait un nom, et avait été étudiée.
Les réponses apportées par les intervenants (en particulier wiwaxia) montrent que c'est une question presque banale (une fois le vocabulaire utilisé bien établi), puisqu'on parle d'extrémum de fonction (quoi de plus "bête" que l'étude d'une fonction pour un matheux )
En tout cas merci à tous !

[tbc92]

@Souviron34

Pour le cas n°3, le point recherché est forcément un des sommets.
Pour s'en convaincre :
- Si on a un seul point, les "courbes-de-niveau" sont des cercles
- Si on a 2 points, les "courbes-de-niveau" sont des ellipses
- Si on a 3 points ou plus, les "courbes-de-niveau" sont des espèces d'ovoïdes. ( courbes quadratiques concaves...)
Et du coup, on voit bien que la courbe de niveau la plus éloignée passe par un des sommets.

[souviron34]

@Souviron34

Pour le cas n°3, le point recherché est forcément un des sommets.

T'as bien raison

J'avais dans la tête le cas du point le plus proche...

Je corrige donc... et j'ajoute un NB qui me semble essentiel...

[souviron34]

Une petite note sur le cas 1 :

• Cas 1 : comme on l'a dit ci-dessus, on a juste un ensemble de points et on cherche une solution générale. Autant il est facile de calculer le barycentre, autant la notion de "point le plus éloigné" est absurde, puisque l'infini est la solution.

Une manière de trouver le PREMIER point le plus éloigné de l'ensemble des points serait :

• Calculer le diagramme de Voronoi des points.
• Parcourir les cellules extérieures trouver le segment le plus éloigné des sommets adjacents.

Ou alternativement :

• Calculer la triangulation de Delaunay
• Explorer chacun des triangles extérieurs et trouver celui ayant les plus longs côtés ET le plus équilatéral.
• Trouver le cercle circonscrit de ce triangle, et le point serait le symétrique du pied de la médiane sur ce cercle

Ou encore :

• Calculer le barycentre
• Trouver le cercle circonscrit englobant tous les points
• Trouver le point le plus proche de la circonférence de ce cercle
• Le point serait le symétrique du barycentre sur ce rayon

Réflexions librement inspirées par http://stackoverflow.com/questions/4...s-bounding-box et autres pointeurs ci-après : http://gis.stackexchange.com/questio...xisting-points et
http://mathoverflow.net/questions/12...s-in-a-polygon (avec une réponse de O'Rourke, pas moins)

et enfin un article intéressant : https://www.uni-konstanz.de/mmsp/pub...s/StHdDo11.pdf