smallest enclosing circle

2022 · interactive · the blog post

The objective is to find the smallest circle that contains all given points on a canvas. Both implementations here are randomized algorithms. They exploit this lemma:

For any finite P in the plane with |P| ≥ 3 there is a subset Q ⊆ P with |Q| = 3 such that C(Q) = C(P).

Here P is the set of all points and C(P) its smallest enclosing circle. In every iteration we randomly select |N| points of P and calculate their circle. If it contains all points we are done.

click to add points, drag to move them.

mode

algorithm

run

|N| = 3iterations: 0

naive algorithm

Every iteration guesses a circle from |N| points drawn with an even distribution, until the guess contains all points.

while true
  choose Q ⊆ P with |Q| = |N| randomly
  calculate C(Q)
  if P is contained in C(Q)
    return C(Q)

Expected runtime O(n⁴).

smart algorithm

The naive algorithm is slow because it guesses with an even distribution every iteration. This one doubles the points that lie outside the guessed circle, so the points that matter become more likely to be drawn. The number next to each point is its multiplicity.

while true
  choose Q ⊆ P with |Q| = |N| randomly
  calculate C(Q)
  if P is contained in C(Q)
    return C(Q)
  double the points of P outside of C(Q)

Expected runtime O(n log n), obtained through probabilistic runtime analysis not covered here.