# finding points with maximum distance between them on a circle

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?

-
What on earth is the surface of a circle???? – Vladimir Jun 21 '14 at 13:22
anything within the radius of the origin (as opposed towards the points that are exactly the radius from the origin), so assuming the origin is in x=0,y=0 any point for which x^2+y^2<radius – Thijser Jun 21 '14 at 13:27
This Wolfram page has a nice animation of the problem. There's a link to download the source code, but I didn't try it. – TonyK Jun 21 '14 at 14:15

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.