I'm a computer science student working on a problem in computer graphics and looking for a formula that can find the x and y positions of a set of N points on the surface of a circle so that the distance between them is maximized.
Currently the solution is to just draw a bunch of random points and then look for the one with the lowest total distance to the others and then pick that, while it works somewhat it's not working well. I'm currently thinking about just cutting my circle into little squares, give each of them a sum distance to all other points and then placing a point on the square with the highest value (first one randomly on the outer part of the circle). However this is neither very efficient nor actually all that accurate so is there a more mathematical model to do this?
Best Answer
Given a set of $N$ points, the distance between one pair of points may not be the same as the distance between some other pair of points. I suppose you want to maximize the minimum of the set of distances between points, measured between all possible pairs of points.
Suppose the resulting distance is $2r$. This means you could draw a disk of radius $r$ around each of your points, and no pair of these disks would overlap (although some pairs of the disks would touch each other). You would then have found a packing of $N$ circles within a circle of radius $R + r$, where $R$ is the radius of your original circle. If you have succeeded in finding the maximum value of the minimum distance between points, this packing of circles will be optimal.
Finding an optimal packing of $N$ circles within a larger circle is a difficult problem. See http://en.wikipedia.org/wiki/Circle_packing_in_a_circle. There are many values of $N$ for which we aren't yet sure we have found an optimal packing; for example, the best known packing for $N = 14$ is only conjectured to be optimal.
In other words, there isn't a simple mathematical formula that will just give you the answer. In practice, you'll probably have to resort so some kind of brute-force method or evolutionary algorithm, and you will never be sure you've found the best possible answer, only that your last answer is better than any of the other ones you've found.