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