Smallest-circle problem

The smallest-circle problem or minimum covering circle problem is a mathematical problem of computing the smallest circle that contains all of a given set of points in the Euclidean plane. The corresponding problem in n-dimensional space, the smallest bounding sphere problem, is to compute the smallest n-sphere that contains all of a given set of points. The smallest-circle problem was initially proposed by the English mathematician James Joseph Sylvester in 1857.Let P be any set of points in the plane, and suppose that there are two smallest enclosing disks of P, of radius with centers at z → 1 {displaystyle {vec {z}}_{1}} and z → 2 {displaystyle {vec {z}}_{2}} . Let r {displaystyle r} be their shared radius, and let 2 a {displaystyle 2a} be the distance between their centers. Since P is a subset of both disks it is a subset of their intersection. However, their intersection is contained within the disk with center 1 2 ( z → 1 + z → 2 ) {displaystyle {frac {1}{2}}({vec {z}}_{1}+{vec {z}}_{2})} and radius r 2 − a 2 {displaystyle {sqrt {r^{2}-a^{2}}}} , as shown in the following image: The smallest-circle problem or minimum covering circle problem is a mathematical problem of computing the smallest circle that contains all of a given set of points in the Euclidean plane. The corresponding problem in n-dimensional space, the smallest bounding sphere problem, is to compute the smallest n-sphere that contains all of a given set of points. The smallest-circle problem was initially proposed by the English mathematician James Joseph Sylvester in 1857. The smallest-circle problem in the plane is an example of a facility location problem (the 1-center problem) in which the location of a new facility must be chosen to provide service to a number of customers, minimizing the farthest distance that any customer must travel to reach the new facility. Both the smallest circle problem in the plane, and the smallest bounding sphere problem in any higher-dimensional space of bounded dimension are solvable in worst-case linear time.