Solution Methodologies for the Smallest Enclosing Circle Problem

Abstract

Given a set of circles C = {c₁, ..., cn}on the Euclidean plane with centers {(a₁, b₁), ..., (an, b_n)}and radii {r₁..., r<n},the smallest enclosing circle (of fixed circles) problem is to find the circle of minimum radius that encloses all circles in C. We survey four known approaches for this problem, including a second order cone reformulation, a subgradient approach, a quadratic programming scheme, and a randomized incremental algorithm. For the last algorithm we also give some implementation details. It turns out the quadratic programming scheme outperforms the other three in our computational experiment.