algorithm - Minimal covering circle -

algorithm - Minimal covering circle -

there n points on plane, how can 1 approximately find minimal radius of circle covers k out of n these points? number n supposed less 10^4.

there lots of information on case k==n in wikipedia, found nil on general case.

given candidate radius r, can find maximum number of points can contained circle of radius r taking every pair (p1, p2) of points , seeing how many points contained each of 2 circles of radius r p1 , p2 on boundary.

knowing this, can binary search smallest r such circle of radius r contains k or more points.

algorithm mathematical-optimization