Va falloir marcher un peu : petite énigme géométrique

[Stratero]

Bonjour tout le monde,

J'ai un ami qui habite à Paris. La station de métro la plus proche de chez lui est à près de 15 min de marche.

Il m'a dit : "J'ai surement choisi le point de Paris qui maximise la distance à la station de métro le plus proche".
J'ai répondu : "Problème intéressant!".

Le problème est donc : comment trouver l'endroit de Paris qui maximise la distance à la station de métro la plus proche?

Pour généraliser et simplifier : on remplace Paris par le carré , soit le nombre de stations de métro à Paris, soit et leurs abscisses et ordonnées, soit la fonction associant à chaque point de Paris la distance euclidienne à la station la plus proche, ie telle que , comment trouver le point ?

Il y a peut être une solution toute bête à laquelle je n'ai pas pensé, je ne sais pas.

C'est juste une petite énigme, donc on peut évidemment simplifier, par exemple en restreignant le domaine de recherche au plus petit polynôme contenant toutes les stations, ou à l'enveloppe convexe des stations.

Quelques remarques en passant : est non-injective et continue. On n'a en général pas unicité de la solution mais on a toujours l'existence. On peut raisonner en considérant une solution, puis en étudiant les stations les plus proches équidistantes de la solution.

Je n'ai pas beaucoup plus d'idées que ca. Si quelqu'un a une solution, une idée, ou une direction dans laquelle chercher, je lui en serai reconnaissant.

[LPFR]

Bonjour et bienvenu au forum.
Intéressant.
Je n'ai pas la solution. Mais je donne une ligne de pensée géométrique qui peut, peut-être, être utile.
Imaginons que l'on dessine un disque bleu de diamètre 'r' autour de chaque station. Les seuls candidats possibles se trouvent dans une zone non encore peinte en bleu. On continue à augmenter le rayon des disques. La solution sera le dernier point à l'intérieur de la zone à être peint en bleu.
On peut déjà conclure que la solution est équidistante au moins de trois stations, sauf si elle se trouve sur le bord de la zone, auquel cas elle sera équidistante d'au moins deux stations.
Au revoir.

[skydancer]

Bonjour,

En associant à chaque stations de metro xi, sa "zone d'influence", c'est à dire l'ensemble des points dont la station de metro la plus proche est xi, on construit ce que l'on appelle un diagramme de Voronoi. Ce qui est intéressant, est que la zone d'influence d'une station de metro est un polygone. Il suffit ensuite de lister les sommets des polygones et garder celui qui maximise la distance à une station de metro. Deuxième choses intéressantes, est que ce point sera forcément situé exactement entre deux ou plusieurs stations de metro...

[Stratero]

Bonjour,

Merci pour vos réponses. La notion de diagramme de Voronoi est intéressante, je ne connaissais pas. Donc déjà une solution possible, celle de Skydancer : construire le diagramme de Voronoi, puis examiner tous les sommets du diagramme.

LPFR, il me semble que votre approche donne aussi une solution. Si le point cherché est équidistant de trois stations, il suffit de construire tout les triangles ayant pour sommet une station et ne contenant aucune autre station, puis de trouver les centres des cercles qui passent par les trois sommets de chacun des triangles. Pour le bord, il suffit d'étudier les points d'intersections des droites équidistantes de deux stations et du bord.

Ces points (les centres des cercles) sont des sommets du diagramme de Voronoi. Je pense, sauf peut être dans des cas particuliers (solution sur le bord), que les deux solutions sont équivalentes.

Merci pour vos solutions, je vais essayer d'implémenter ca sur MATLAB.

[LPFR]

Re.
L'avantage de la méthode donné par Skydancer est que l'algorithme existe. Regardez "diagramme de Voronoi" dans wikipedia.
L'algorithme est en n.log(n) (ce qui est mieux que n²).
A+

[Penelope20k]

Je n'ai pas les capacité mathématiques pour resoudre ce probleme, mais ne peut on pas considerer le barycentre de l'ensemble des station associé à un poids -p
et faire varier le poids p pour que les coordonnées du barycentre appartienne au carré ?

[LPFR]

Bonjour.
Non. Vous ne pouvez pas remplacer un problème qui est difficile en lui même, par un autre qui ne l'est pas. Les gens qui ont pondu l'algorithme dont j'ai fait référence ne sont pas des idiots. Si le problème avait pu être résolu plus simplement, ils l'auraient fait.
Avez-vous regardé l'algorithme?
Au revoir.

[Deedee81]

Salut,

De toute façon, il suffit d'avoir des poids tous identiques. Dans ce cas, le barycentre sera toujours dans le carré et il est clair que ce n'est pas la solution.

[Penelope20k]

Oui et non LPFR.

Je dis pas que Voronoï est un trou du cul, mais Voronoï recherche des ensembles de points (donc une infinitié).Il decompose un ensemble en sous ensemble.

alors qu'ici, on est simplement dans un plan (2D) et l'on cherche un point.

Comme je l'ai dit je n'ai pas les capacités pour le faire, mais ce point que l'on cherche ca ne serait pas un barycentre ? (C est juste une interogation, parceque intuitivement ce point est le point le plus distant de toutes les stations de metro)

mais est ce que le point le plus distant de toute les station de metro correspond bien au point qui maximise la distance à la station de métro la plus proche ?

[LPFR]

Oui et non LPFR.

Je dis pas que Voronoï est un trou du cul, mais Voronoï recherche des ensembles de points (donc une infinitié).Il decompose un ensemble en sous ensemble.

alors qu'ici, on est simplement dans un plan (2D) et l'on cherche un point.

Comme je l'ai dit je n'ai pas les capacités pour le faire, mais ce point que l'on cherche ca ne serait pas un barycentre ? (C est juste une interogation, parceque intuitivement ce point est le point le plus distant de toutes les stations de metro)

mais est ce que le point le plus distant de toute les station de metro correspond bien au point qui maximise la distance à la station de métro la plus proche ?

Re.
Non. Voronoi trouve des polygones et ce sont les sommets de ces polygones, qui sont en nombre limité, qui intéressent. Et non l'ensemble des points des arêtes ou de l'intérieur des polygones.
Et c'est un des sommets trouvés par Voronoi qui est la solution.
Je ne vois pas de rapport avec un barycentre. Le barycentre de trois points n'est pas, en général, le point le plus éloigné.
De plus quels 3 points? C'est ça un des problèmes d'un algorithme: ne pas traiter . Mais des triades de sommets premiers voisins.
A+

[Penelope20k]

comme quoi:

le lien avec les barycentres n'était pas si idiot.

http://www.ai.univ-paris8.fr/~audibe...angulation.pdf
voir page 7

[Deedee81]

Ce n'est pas parceque le mot barycentre est cité dans l'article (et solution dans le cas de trois points), UNE fois, que la méthode décrite dans le message 6 peut marcher.

Personne n'avait d'ailleurs traité l'idée d'idiote !!!!

[Penelope20k]

Bonjour.
Non. Vous ne pouvez pas remplacer un problème qui est difficile en lui même, par un autre qui ne l'est pas. Les gens qui ont pondu l'algorithme dont j'ai fait référence ne sont pas des idiots. Si le problème avait pu être résolu plus simplement, ils l'auraient fait.
Avez-vous regardé l'algorithme?
Au revoir.

bah si justement.....
je posais juste une question et on m'a pris de haut...

[Penelope20k]

c'est pour cela que je me suis peut etre emporter un peu...
d'ailleurs j'ai largement preferé ta reponse à celle de LPFR

[Deedee81]

bah si justement.....

Ah oui, le mot était bien dans la phrase, ça m'avait échappé