Discussion :

[Nemerle]

Salut, comment-y k'est-ce qu'on fait avec le truc suivant: dans une compact connexe K du plan, comment choisir N points K tel que

- toute paire de points a un distance supérieur à une constante C
- la somme de ces distances est minimale

Gné?

[pseudocode]

En faisant du circle packing dans un compact ?

[Nemerle]

Nan, passqu'euh mon nombre de points N et mon D est petit par rapport à mon compact.

En fait Pseudocode, si tu veux le détail, voila:

mon K est décomposé en un pavage de "briques", et il y a en a beaucoup. Je veux decomposer mon K en N ensembles disjoints de briques, ensembles qui doivent tous avoir "à peu près" la meme taille. Ensuite, je vous trouver une brique dans chacun des N ensembles de telle sorte que la somme des distances entre ces N briques soit minimale.

[pseudocode]

Et bien heu... y a donc deux problèmes distincts ?

1. décomposer K en N ensembles disjoints qui ont tous a peu près la même taille
2. trouver un circuit de N points (chacun dans un ensemble) qui soit de longueur minimale

Ou alors les deux problèmes sont liés ? Il faut décomposer K de telles facon que le circuit soit minimum ?

[Nemerle]

oui 1 est aussi un problème!! Mais disons pour simplifier que tu fais un Voronoï en N-morceaux et tu passes au problème 2...


(mais si tu sais optimiser d'un coup 1+2, I take)

[pseudocode]

oui 1 est aussi un problème!! Mais disons pour simplifier que tu fais un Voronoï en N-morceaux et tu passes au problème 2...

Hum... pas évident. Mathématiquement, vu qu'on est dans un cas continu je suppose qu'on doit pouvoir utiliser les multiplicateurs de Lagrange.

Mais ca serait moi, je ferais de multiples essais avec un algo simplex (Nelder–Mead).

(mais si tu sais optimiser d'un coup 1+2, I take)

Heu... non.