Given a set of points, what's a good algorithm, if any, for determining the center of a circle that is of a fixed size so that as many of these points as possible are covered by the circle?
Thanks
[Edited by - Laccolith on August 14, 2010 6:19:49 PM]
Place a circle to cover as many points in a set as possible
I can get you started on a bad algorithm:
If there's one point, it's easy, so suppose we have more than one.
Given an optimal solution, we can always shift the circle over so that at least two points are on the edge of the circle, and still be optimal.
Therefore, for each pair of points, place the circle so it lies on the two points -- there are 2 ways to do this for each set of points. Then count how many points are in the circle,
So we have O(n^2) circles to try, each costing O(n) to count how many points are inside. Totaling a O(n^3) time complexity.
There's likely a better algorithm than this, but it's a start
If there's one point, it's easy, so suppose we have more than one.
Given an optimal solution, we can always shift the circle over so that at least two points are on the edge of the circle, and still be optimal.
Therefore, for each pair of points, place the circle so it lies on the two points -- there are 2 ways to do this for each set of points. Then count how many points are in the circle,
So we have O(n^2) circles to try, each costing O(n) to count how many points are inside. Totaling a O(n^3) time complexity.
There's likely a better algorithm than this, but it's a start
The question is lacking some constraints...
As stated, an acceptable solution would be a random point (say, (0,0)) with appropriate radius (O(n) to find the radius). But 'finding' the center is O(1).
I think you need to specify some condition which has to be balanced. Maybe minimize the radius? But then what's 'many points'?
Edit: disregard, misread. The radius is fixed...
As stated, an acceptable solution would be a random point (say, (0,0)) with appropriate radius (O(n) to find the radius). But 'finding' the center is O(1).
I think you need to specify some condition which has to be balanced. Maybe minimize the radius? But then what's 'many points'?
Edit: disregard, misread. The radius is fixed...
is it actually points you're after, or are they part of the story?
to explain my question, consider that you have two points. are you interested in capturing as much of the line between them as possible? If so, you'd position the circle at the midpoint between them. However, if the distance between the points is greater than the diameter of the circle, positioning the circle at the midpoint envelope zero points; if you were after the points themselves, you'd need to choose one or the other!
to explain my question, consider that you have two points. are you interested in capturing as much of the line between them as possible? If so, you'd position the circle at the midpoint between them. However, if the distance between the points is greater than the diameter of the circle, positioning the circle at the midpoint envelope zero points; if you were after the points themselves, you'd need to choose one or the other!
The problem is similar to the general clustering problem. I think if you're looking for approximate/good-enough solutions you might read up on clustering algorithms; in particular QT clustering with the maximum diameter set appropriately. But I haven't really thought it through.
Anyway, my intuition is that this is a hard problem...
Anyway, my intuition is that this is a hard problem...
You could approximate it by for example taking a surface of 1000x1000 pixels, and draw filled circles with additive blending at each point, with the same radius as the circle that is supposed to contain the points. This way each pixel where the circle can be located to contain the point in question will have its brightness increased. Then search the image for the brightest pixel to find the best spot to place the circle.
Author
Yea, I'm after the points, imagine there are some bugs on the floor and I have a single cup to place over them, I'm trying to catch as many as possible under the cup.
I had a go at figuring it out, though I'm not sure how optimal it is. This is what I'm doing in Pseudocode:
Then the points left in the set should be covered by the circle placed at its average.
I had a go at figuring it out, though I'm not sure how optimal it is. This is what I'm doing in Pseudocode:
DO Calculate mean average of all points Select point furthest from this average IF its further than our fixed size from the average Remove from setWHILE <Point has been removed from set>Then the points left in the set should be covered by the circle placed at its average.
A scenario that wouldn't work with the mean average thing would be if all the points made up a circle with a bigger radius than the "cup". then it would be placed in the center and get none of the "bugs". In that case it would be better to place the circle at the side.
If worst comes to worst, I have a recursive algorithm that would work, based on spatial partioning and octrees. Divide the space up into really large coarse grid cells. Each point imagines that it's a circle of the same radius as the "cup". Then it finds every grid cell it intersects and adds to the counter (integer). The grid cells should also contain list of all the points that touch it.
It goes down another level, perhaps where the cells are half the original size. The grid cells only iterate through the list of particles that touch it. Each of these points add to the smaller cells' counters and we keep on going down level by level and once you've reached an accuracy you're content with you use the position of that grid cell.
If worst comes to worst, I have a recursive algorithm that would work, based on spatial partioning and octrees. Divide the space up into really large coarse grid cells. Each point imagines that it's a circle of the same radius as the "cup". Then it finds every grid cell it intersects and adds to the counter (integer). The grid cells should also contain list of all the points that touch it.
It goes down another level, perhaps where the cells are half the original size. The grid cells only iterate through the list of particles that touch it. Each of these points add to the smaller cells' counters and we keep on going down level by level and once you've reached an accuracy you're content with you use the position of that grid cell.
Instead of starting with the mean average, you could go with the max distance.
It gives you an already good first circle (the diameter being the two points with the max distance)
Then you could go for a quick computation of "how the circle has to be efficiently modified to get all the points?".
I think that computing the average of the vectors from the center to all the outside points should give you a good "growing direction clue".
Then make it grow step by step according to that until it contains all the points.
You can do that by dichotomy if you want to have some more fun :D
Anyway, that is just a heuristic method, but the last part makes sure you don't miss any point.
It gives you an already good first circle (the diameter being the two points with the max distance)
Then you could go for a quick computation of "how the circle has to be efficiently modified to get all the points?".
I think that computing the average of the vectors from the center to all the outside points should give you a good "growing direction clue".
Then make it grow step by step according to that until it contains all the points.
You can do that by dichotomy if you want to have some more fun :D
Anyway, that is just a heuristic method, but the last part makes sure you don't miss any point.
If each point is a circle and the circle is a point, you want to place the point in as many circles as possible. One approximation would be to render each circle with additive color and find the brightest area.
HLSL:
For each pixel, loop in an array of all circles and measure the distance. Add something to the color if it is inside.
HLSL:
For each pixel, loop in an array of all circles and measure the distance. Add something to the color if it is inside.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
