I have been posed a problem in class which asks me to find an algorithm that finds a circle that encloses at most 12 points on a grid 2000.00 by 2000.00, no matter where the circle is centered, given a random set of points. I can't think of the first thing to try here. Please someone help.
Is this a circle of the same radius, but arbitary centre?
If the radius can be different depending on the centre try this (all units are
in grid pitch units):
RonLCode:centre=(a,b) Rlo=0.5 Rhi=2000.0 If point at (a,b) Nlo=1 Else Nlo=0 Endif Nhi = total number points (assumed >12) Repeat { Rwrk=(Rhi+Rlo)/2 Nwrk=number of points enclosed by circle centred at (a,b) of radius Rwrk If Nwrk==12 break Endif If Nwrk>=12 Rhi=Rwrk Else If Nwrk<12 Rlo=Rwrk Endif } Return Rwrk
The number of points is random, as well as their position.
Thanks for the algorithm Captain, but it is arbitary center point, same radius at all points as far as i can tell.
Here is the actual question:
Background: Something about breeding toads in the "Paranta Forest".
"Given the positions of the female toads in the Paranta forest, and assuming that no male toads have yet been released, work out the largest territory for a male toad that, no matter where you put it, will not enclose more than 12 females. A toads territory can be generalised to a circle centered on that toad."
2000x2000 is a small number of grid points for a modern computer, so brute force should solve this.
Loop over grid points
calculate the distance to 13 closest females
end loop
required radius is anyting less than the mininmum of the distances just calculated.
You may have to do some pre-sorting of the females positions to make the
calculation practical.
Even if this won't execute in a reasonable time, the question does not seem to ask that the algorithm be practical
RonL