Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
What on earth is the surface of a circle???? –  Vladimir Jun 21 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 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 at 14:15

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.