Pareil, je suis pas assez matheux. Mais effectivement, ça ressemble fortement aux problèmes de théorie des graphes.
Par exemple : http://en.wikipedia.org/wiki/Delaunay_triangulation (mais je sais pas si ça respecte tes critères)

Y'a bien quelqu'un qui pourrait probablement t'aider, mais il aime pas les jeux propriétaires

Au passage, tu as combien de points ? C'est pour savoir si on peut utiliser de la force brute ou pas.