A circle optimization problem
Author
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.
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?
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.
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.
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.
if i undestood him right,
rC is given and you can not set it.
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 JohnBolton
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.
if i undestood him right,
rC is given and you can not set it.
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.
#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...
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...
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
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
