Bonjour enzo,

Soit une suite de point (A_i)i appartenant à R²

On utilise les connexions de la question :

A tout point A_i on associe le disque FERMé de centre A_i et de rayon egal à la longueur minimal de la conexion (si la connexion avec un autre point et un segment !) notons cela r_i...

Notons H l'union de tous ces disques, alors si un point B apparait dans R²\H le graph ne subira au maximum n nouvelle connexions, toutes liées à B, n étant le maximum que la variable i puisse prendre...


Je dis peut etre une betise !

salut,

c'est sans certitude, il y a peut-être des erreurs, mais la premiere idée qui me vient est la suivante.

On teste d'abord quelles sont les connexions cassées, pour cela, à chaque connexion, on procède ainsi,
soit c la longueur de la connexion (la distance entre les deux points) et a et b les distances du nouveau point à ses deux sommets

alors le nouveau point casse la connexion si a²+b²<c² (car l'angle formé par les trois points est obtus)

cette algorithme est linéaire en le nombre de sommets car dans un graphe planaire le nombre d'aretes est inférieur ou égal à 3S-6 où S est le nombre de sommets, et chaque opération effectuée par aretes se fait en temps constant.

Apres pour chercher les nouvelles connexions, je n'ai que trouvé une solution en n.ln n, mais assez tordue, alors je vais encore chercher

Sauf erreurs,

bret

C'est ce que je lui ai expliqué par msn, on doit oublier le sujet ^^

Merci pour vos réponses

Cependant, pour contredire Mahow, ce sujet n'est pas à oublier!!

J'ai exploré deux solutions que j'ai programmées hier :

- la recherche d'un fermé autour du point requête (celui qu'on veut insérer) à partir d'angles orientés.
- une solution se basant sur les digrammes de Voronoï (je ne détaille pas, si vs voulez l'article référence, je vs le passe).

La deuxième donne des résultats tout à fait satisfaisants (justes quoi), et la première pose le problème des points en bordure du plan (= il n'existe pas toujours un fermé autour du point requête).

Je voudrais rajouter pour préciser un peu plus :
- un point peut avoir plusieurs voisins
- il est évident qu'un point et son plus proche voisin ont une connexion.


Le problème étant résolu dans R², je m'attaque maintenant au problème dans R^p p>2.

L'idée est toujours la même. Deux points i et j sont voisins ssi l'hypershpère de centre O (O milieu de [ij]) et de diamètre [ij] ne contient aucun autre point.
Les diagrammes de Voronoï ne marchent qu'en 2D et les angles orientés n'existant que dans un plan, les deux solutions précédentes sont compromises.

Alors si vous avez des idées...
Merci


P.S: L'heuristique que j'utilise est la suivante:
- on cherche le plus proche voisin du point à insérer (M) (admettons ) la distance entre M et vaut d1
- on cherche le voisin le plus éloigné de (i.e, un point ayant une connexion avec et dont la connexion est la plus "grande")  (admettons ). La distance entre et vaut d2.

Tous les points à explorer sont dans l'hypersphère de rayon (d1+d2) * (1+e) avec 0 < e < 1.
En fixant un e >0, j'obtiens toujours les mêmes résultats qu'en reconstruisant entièrement le graphe. j'ai testé ceci sur 15 jeux de données différents.

Si considère un point de R^p, on donne l'hypersphère quand r croit, ce qui fait que le premier point rencontré sur la sphère aura une connection, soit un l'ypersphère de ce point de rayon non nul, on a l'intersection de ces deux hypersphère qui est un cercle, selon r et le second rayon (ainsi que le rayon du cercle engendré) on aura les coordonnée du poit lié...

Mahow,

Dans ta proposition, comment fixes-tu r ?

Je ne le fixe pas, je le considère comme quand il evolue... Un agrandissement de la super sphère en continu (homotétie de centre de la hypersphère et de rapport r pour les calculs analytiques)

Ok, mais le problème est alors l'incrémentation de l'agrandissement. Pour chaque agrandissement, il faut chercher parmi tous les points (au nombre de n) ceux qui sont contenus dans l'hypersphère. A chaque pas de l'algorithme, tu ajoutes une complexité de n. Et au final, tu obtiens une complexité du genre O(xn) où x est le nombre d'itérations..

Au final, je risque même de me retrouver avec une complexité supérieure à celle de l'algo de construction global.

Je rappelle que mon problème n'est pas uniquement de contruire le graphe, mais de chercher la méthode la plus rapide possible et exacte (qui n'existe peut-être pas).