Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Smallest-circle problem
open-in-new
<p>The smallest-circle problem (also known as minimum covering circle problem, bounding circle problem, least bounding circle problem, smallest enclosing circle problem) is a <a href="/facts/Computational_geometry/eeaotQtl">computational geometry</a> problem of computing the smallest <a href="/facts/Circle/9fy5ggKn">circle</a> that contains all of a given <a href="/facts/Set_(mathematics)/BfucfHMq">set</a> of <a href="/facts/Point_(geometry)/6YPAvX2a">points</a> in the <a href="/facts/Euclidean_plane/tAUtRFcn">Euclidean plane</a>. The corresponding problem in <a href="/facts/N-dimensional_space/0ktmUyac"><i>n</i>-dimensional space</a>, the <a href="/facts/Smallest_bounding_sphere/0lVclU4z">smallest bounding sphere</a> problem, is to compute the smallest <a href="/facts/N-sphere/bFu2S7E2"><i>n</i>-sphere</a> that contains all of a given set of points. The smallest-circle problem was initially proposed by the English mathematician <a href="/facts/James_Joseph_Sylvester/6NNurKJH">James Joseph Sylvester</a> in 1857. </p><p>The smallest-circle problem in <a href="/facts/Plane_(geometry)/tAUtRFcn">the plane</a> is an example of a <a href="/facts/Optimal_facility_location/ssbU6ww2">facility location problem</a> (the <a href="/facts/1-center_problem/pMswe7RR">1-center problem</a>) 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 <a href="/facts/Worst-case_complexity/kqzQkwIc">worst-case</a> <a href="/facts/Linear_time/77T62gmf">linear time</a>. </p>