# A circle optimization problem

This topic is 5123 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

In 2D space, given a radius rc of a circle C, several points p1, p2, ..., pn (n<=10), and another circle D ( the radius of D is rd, and center is Cd) Find the center of C (denoted as Cc) such that C can include the most points. However, Cc must be in D and be the point most closest to Cd of the solutions. The solution of Cc can not be the best but the algorithm must be efficient, because the algorithm executes on-the-fly. Thank you in advance.

##### Share on other sites
Do you have any simplifying assumptions or other information about the relative distances/magnitudes? If the pointes tend to be tightly grouped relative to the radii of the circles near the center of D, then the algorithm for that situation might be different than if the points tend to be randomly distributed in an area of greater magnitude than the radii of C and D. Also, what are rough relative sizes of C and D?

##### Share on other sites
I'm working on it right now, I'll give you an answer later on today...

##### Share on other sites
Either this is a trick question or you need to come up with better requirements.

The answer is trivial. CC is simply CD and rC is the distance to the farthest point. This solution satisfies all your requirements: it is efficient, C includes all the points, CC can be no closer to CD and is in D.

##### Share on other sites
Tricky question, really. I don't think there are any simple ideal solution (the only one i can think of is voronoi-like partitioning of plane into areas by number of points included)

And seems that to make good non-ideal it's needed to know more about distribution of your points. Maybe simple average position will do the job, maybe not.

Quote:
 Original post by JohnBoltonEither this is a trick question or you need to come up with better requirements.The answer is trivial. CC is simply CD and rC is the distance to the farthest point. This solution satisfies all your requirements: it is efficient, C includes all the points, CC can be no closer to CD and is in D.

if i undestood him right,
rC is given and you can not set it.

##### Share on other sites
Maybe overlay a grid over the circle then at each grid point within the circle find the point with the lowest sum of the squared distances. Start with a relatively large grid then subdivide, i.e. check +/- half the grid spacing. It won't find you the global minimum, but might get you to a reasonable local minimum. Seems like an AI problem and often with AI you just want reasonable rather than absolute optimumal to simplify the problem.

##### Share on other sites
#define N 1000

I would try just testing N random locations of the center and picking the best found.

Adjust N to make the algorithm run within your constrains. If this doesn't give you good enough results, think harder...

##### Share on other sites
Sorry wasn't logged in..

The set below was a bit messed up :)

S = { Cc | Cc in D and Pn in C }, where Pn = {P0..PN}, N<=10 N>M
where M is some pre-chosen value.

The real solution is then simply the Cc in S thats closest to Cd

1. 1
2. 2
3. 3
Rutin
25
4. 4
5. 5
khawk
14

• 11
• 11
• 23
• 10
• 9
• ### Forum Statistics

• Total Topics
633649
• Total Posts
3013117
×