# Thread: Maximum circle enclosing 12 points

1. ## Maximum circle enclosing 12 points

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.

2. Originally Posted by circleBounding
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.
how many random points are we talking here?

3. Originally Posted by circleBounding
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):

Code:
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
RonL

4. 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."

5. Originally Posted by circleBounding
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

6. problem is, it is in float accuracy, so it is actually 200,000*200,000 distinct points. Also, in the class I'm doing, efficiency is key, so the algorithm has to run very quickly