Minimum Enclosing Circle

The minimum enclosing circle is the smallest disk containing every input point. Unlike a bounding box, it can rotate freely and has a unique optimal center for a nonempty finite set. Its boundary is supported by at most three points. A randomized incremental algorithm exploits this small support to achieve expected linear time, while its nested loops remain easy to implement and test against small exhaustive examples.

Prerequisites: Circle geometry; line equations; randomized incremental reasoning.

Build the idea

1. Identify the support

   One point needs radius zero. Two boundary points define a diameter circle. Three noncollinear support points define a circumcircle; a collinear triple is enclosed by the diameter of its farthest pair. A true three-point minimal support forms an acute triangle; otherwise a pair suffices. These facts explain why rebuilding only small boundary configurations can recover the optimum.

2. Insert in random order

   Shuffle the input, then maintain the minimum circle for the processed prefix. If a new point is inside, nothing changes. If it lies outside, it must be on the boundary of the new optimum: otherwise the disk could be adjusted before reaching it. Start a radius-zero circle at that point and reprocess earlier points while preserving this boundary requirement.

   $$2z·(B-A)=|B-A|\mathrm{²}$$

3. Rebuild with two and three constraints

   If an earlier point is outside the current disk, use the diameter circle through it and the new point. Scan the still-earlier prefix again; an outside third point forces a circle through all three. The nested loops implement incremental subproblems with one and then two fixed boundary points. They are not an unrestricted greedy choice of three arbitrary points.

4. Construct a circumcenter

   Translate a triple by A. The circumcenter offset z satisfies 2z·(B−A)=|B−A|² and the analogous equation for C. Solve the two-by-two system using its determinant. Exact zero determinant on the bounded integer inputs identifies collinearity and falls back to the farthest-pair diameter. Translating first reduces cancellation relative to expanding absolute coordinate squares.

5. Understand expected cost and sample

   A random prefix has at most three support points. The chance its last random point forces an outer rebuild is at most 3/i; analogous smaller-support reasoning bounds the nested work, yielding expected O(n). A deliberately bad fixed order can take cubic time. For four corners (±1,±1), the center is (0,0) and radius √2. The code shuffles using a random engine; tolerance affects near-boundary decisions and is not exact arithmetic.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
#include<random>
#include<cmath>
#include<iomanip>
struct Point{
    long double x,y;
    Point operator-(Point p)const{
        return {x-p.x,y-p.y};
    }
};
long double distance(Point a,Point b){
    return std::hypotl(a.x-b.x,a.y-b.y);
}
struct Circle{
    Point center;
    long double radius;
};
bool contains(Circle c,Point p){
    return distance(c.center,p)<=c.radius+1e-8L;
}
Circle pairCircle(Point a,Point b){
    Point center{(a.x+b.x)/2,(a.y+b.y)/2};
    return {center,distance(a,b)/2};
}
Circle tripleCircle(Point a,Point b,Point c){
    Point u=b-a,v=c-a;
    long double det=2*(u.x*v.y-u.y*v.x);
    if(det==0){ // Integer input makes an exactly collinear determinant exactly zero here.
        Circle answer=pairCircle(a,b),ac=pairCircle(a,c),bc=pairCircle(b,c);
        if(ac.radius>answer.radius){
            answer=ac;
        }
        if(bc.radius>answer.radius){
            answer=bc;
        }
        return answer;
    }
    long double uu=u.x*u.x+u.y*u.y,vv=v.x*v.x+v.y*v.y;
    Point center{a.x+(uu*v.y-vv*u.y)/det,a.y+(u.x*vv-v.x*uu)/det};
    return {center,distance(center,a)};
}
int main(){
    int n;
    std::cin>>n;
    std::vector<Point>p(n);
    for(auto&a:p){
        std::cin>>a.x>>a.y;
    }
    std::mt19937 engine(std::random_device{}());
    std::shuffle(p.begin(),p.end(),engine);
    Circle circle{{0,0},-1};
    for(int i=0;i<n;++i){
        if(!contains(circle,p[i])){
            circle={p[i],0};
            for(int j=0;j<i;++j){
                if(!contains(circle,p[j])){
                    circle=pairCircle(p[i],p[j]);
                    for(int k=0;k<j;++k){
                        if(!contains(circle,p[k])){
                            circle=tripleCircle(p[i],p[j],p[k]);
                        }
                    }
                }
            }
        }
    }
    std::cout<<std::fixed<<std::setprecision(6)<<circle.center.x<<' '<<circle.center.y<<' '
                <<circle.radius<<'\n';
}

Complexity analysis

Expected O(n) time over the random permutation, worst-case O(n³) for unfavorable order. O(n) point storage; O(1) extra geometric state. The shuffle is linear. This is a numerical implementation, so the combinatorial bound describes the ideal predicate model.

Example input and output

Read n (1..100000), then integer points with coordinates within ±10^4. Print approximate center x y and radius to six decimals. Duplicate and collinear points are allowed; containment uses absolute distance tolerance 10^−8.

Input

4
-1 -1
1 -1
1 1
-1 1

Output

0.000000 0.000000 1.414214

A diagonal is a diameter of length 2√2; all four corners lie on the circle centered at the origin.

Practical applications

Use to choose a smallest circular covering region or facility radius. For small n, enumerating pair/triple circles gives a useful test oracle but is much slower. A convex hull can discard interior points, although it adds sorting cost and is not required.

Check your understanding

What does random shuffling change?

Put it into practice

Compare small random sets with all containing pair/triple candidate circles.