Smallest-Circle Problem¶

The smallest-circle problem (also known as minimum covering circle problem, bounding circle problem, least bounding circle problem, smallest enclosing circle problem) is a computational geometry problem of computing the smallest circle that contains all of a given set of points in the Euclidean plane.

Version: v1 · 2026-09-28 · History
Domain-specific #: 12091
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomains: Computational Geometry, Geometric Optimization → Computer Science & Software Engineering

Core Idea¶

Smallest-Circle Problem is treated here as the recurring computational geometry identity summarized by this source-grounded definition: The smallest-circle problem (also known as minimum covering circle problem, bounding circle problem, least bounding circle problem, smallest enclosing circle problem) is a computational geometry problem of computing the smallest circle that contains all of a given set of points in the Euclidean plane.

The smallest-circle problem (also known as minimum covering circle problem, bounding circle problem, least bounding circle problem, smallest enclosing circle problem) is a computational geometry 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. Since is minimal, we must have \sqrt{r^2-a2}=r , meaning a=0 , so the disks are identical.

For Smallest-Circle Problem, the abstraction is narrower than the article's general subject matter: a positive case must preserve The smallest-circle problem (also known as minimum covering circle problem, bounding circle problem, least bounding circle problem, smallest enclosing circle problem) is a computational geometry problem of computing the smallest circle that contains all of a given set of points in the Euclidean plane. Retaining only the name, a familiar example, or a downstream effect is insufficient. The specialist roles and tests remain anchored in computational geometry, which is why this identity is domain-specific rather than prime.

Structural Signature¶

Sig role-phrases:

Defining carrier — The line q in the direction is placed to go through an intersection such that there are \frac{n}{8} intersections in each half-plane defined by the line (median position).
Constitutive relation — It also states that performance is improved by dynamically re-ordering the points so that those that are found to be outside a circle are subsequently considered earlier, but this requires a change in the structure of the algorithm to store P as a "global".
Operating condition — The minimum covering circle of a set S can be determined by at most three points in S which lie on the boundary of the circle.
Recognition evidence — If it is determined by only two points, then the line segment joining those two points must be a diameter of the minimum circle.
Admissible variation — If it is determined by three points, then the triangle consisting of those three points is not obtuse.
Characteristic consequence — Subsequently, the smallest-circle problem was included in a general class of LP-type problems that can be solved by algorithms like Welzl's based on linear programming.
Failure boundary — Megiddo's algorithm is based on the technique called prune and search, reducing the size of the problem by removing \frac{n}{16} unnecessary points.

What It Is Not¶

Not the whole field of computational geometry. The node requires the specific identity stated by The smallest-circle problem (also known as minimum covering circle problem, bounding circle problem, least bounding circle problem, smallest enclosing circle problem) is a computational geometry problem of computing the smallest circle that contains all of a given set of points in the Euclidean plane.
Not an over-broad reading. If it is determined by three points, then the triangle consisting of those three points is not obtuse.
Not an over-broad reading. However, their intersection is contained within the disk with center \frac 12 (\vec{z}_1+\vec{z}_2) and radius \sqrt{r^2-a2} , as shown in the following image.
Not an over-broad reading. The line q′ in the direction is placed to go through an intersection such that there are \frac{n}{16} intersections in each half of the half-plane not containing the solution.
Not automatically 1-Center Problem. Retrieval proximity does not establish equivalence; the two identities must be compared by carrier, operation, and failure boundary.

Scope of Application¶

Smallest-Circle Problem applies literally inside computational geometry wherever the source-defined carrier and relation can be established. Its documented habitats include:

Emo Welzl proposed a simple randomized algorithm for th. As a consequence of membership in this class, it was shown that the dependence on the dimension of the constant factor in the O(n) time bound, which was factorial for Seidel's method, could be reduced to subexponential.
Megiddo's algorithm. The solution of the subproblem is either the solution of the unconstrained problem or it is used to determine the half-plane where the unconstrained solution center is located.
Other algorithms. Chakraborty and Chaudhuri propose a linear-time method for selecting a suitable initial circle and a pair of boundary points on that circle.
Other algorithms. Each step of the algorithm includes as one of the two boundary points a new vertex of the convex hull, so if the hull has h vertices this method can be implemented to run in time O(nh).
Other algorithms. At each step, a point not covered by the current sphere is used to find a larger sphere that covers a new subset of points, including the point found.
Other algorithms. The complexity of the method has been analyzed by Drezner and Shelah.

Outside computational geometry, the name should be retained only when these same operational conditions survive; otherwise the comparison belongs to the broader parent 1 Center Problem or should be marked as analogy.

Clarity¶

A clear use of Smallest-Circle Problem names the carrier, the operative relation, and the conditions under which the source treats the identity as present. The minimal definition is The smallest-circle problem (also known as minimum covering circle problem, bounding circle problem, least bounding circle problem, smallest enclosing circle problem) is a computational geometry problem of computing the smallest circle that contains all of a given set of points in the Euclidean plane. The strongest recognition evidence in the frozen account is: If it is determined by only two points, then the line segment joining those two points must be a diameter of the minimum circle. A report should distinguish that evidence from a proxy, consequence, or common implementation. It should also state the qualification If it is determined by three points, then the triangle consisting of those three points is not obtuse. so that a reader can reproduce the classification rather than infer it from topical resemblance.

Manages Complexity¶

Smallest-Circle Problem compresses multiple computational geometry details into a stable diagnostic relation. The source shows both the central mechanism—it also states that performance is improved by dynamically re-ordering the points so that those that are found to be outside a circle are subsequently considered earlier, but this requires a change in the structure of the algorithm to store P as a "global".—and the practical consequence—subsequently, the smallest-circle problem was included in a general class of LP-type problems that can be solved by algorithms like Welzl's based on linear programming. This compression makes cases comparable while leaving parameters, conventions, exceptions, and evidential quality explicit. It is lossy by design: local history and implementation details may be omitted only when they do not alter the defining relation.

Abstract Reasoning¶

Type the carrier. Identify the computational geometry entities to which the claim applies.
State the relation. Use the source-grounded identity: The smallest-circle problem (also known as minimum covering circle problem, bounding circle problem, least bounding circle problem, smallest enclosing circle problem) is a computational geometry problem of computing the smallest circle that contains all of a given set of points in the Euclidean plane.
Check operation and conditions. The minimum covering circle of a set S can be determined by at most three points in S which lie on the boundary of the circle.
Demand recognition evidence. If it is determined by only two points, then the line segment joining those two points must be a diameter of the minimum circle.
Test variation. Change an implementation or setting while preserving if it is determined by three points, then the triangle consisting of those three points is not obtuse.
Run the collapse test. Remove the defining operation; if the label still seems equally apt, only a topic or correlate was retained.
Reduce cautiously. When the specialist conditions cannot be carried, route the residual comparison to 1 Center Problem.

Knowledge Transfer¶

Within the home domain. Knowledge about Smallest-Circle Problem transfers literally when a new case preserves the same carrier type, relation, and recognition test. As a consequence of membership in this class, it was shown that the dependence on the dimension of the constant factor in the O(n) time bound, which was factorial for Seidel's method, could be reduced to subexponential. The solution of the subproblem is either the solution of the unconstrained problem or it is used to determine the half-plane where the unconstrained solution center is located.

Beyond the home domain. No canonical parent is asserted for Smallest-Circle Problem. An outside case receives the specialist name only when the same typed roles and rejection conditions can be filled literally; otherwise the comparison remains an analogy pending later graph densification.

Examples¶

Canonical¶

At each step, a point not covered by the current sphere is used to find a larger sphere that covers a new subset of points, including the point found. This case is canonical because it supplies a concrete carrier and lets the defining relation be checked rather than merely named.

Mapped back: carrier → the entities in the documented case; operation → The smallest-circle problem (also known as minimum covering circle problem, bounding circle problem, least bounding circle problem, smallest enclosing circle problem) is a computational geometry problem of computing the smallest circle that contains all of a given set of points in the Euclidean plane; recognition evidence → If it is determined by only two points, then the line segment joining those two points must be a diameter of the minimum circle

Applied / In Practice¶

Although its worst case running time is O(h 3 n), the authors report that it ran in linear time in their experiments. The applied case shows how the identity is used under a second setting or qualification while keeping the same operative relation.

Mapped back: changed setting → Other algorithms; invariant → The smallest-circle problem (also known as minimum covering circle problem, bounding circle problem, least bounding circle problem, smallest enclosing circle problem) is a computational geometry problem of computing the smallest circle that contains all of a given set of points in the Euclidean plane; boundary → the case exits the class when if it is determined by three points, then the triangle consisting of those three points is not obtuse

Structural Tensions¶

T1 — Stable identity versus admissible variation. If it is determined by three points, then the triangle consisting of those three points is not obtuse. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Which changes preserve the defining relation, and which replace it?

T2 — Recognition versus proxy. However, their intersection is contained within the disk with center \frac 12 (\vec{z}_1+\vec{z}_2) and radius \sqrt{r^2-a2} , as shown in the following image. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Does the cited evidence establish the identity or only a correlated sign?

T3 — Definition versus implementation. The line q′ in the direction is placed to go through an intersection such that there are \frac{n}{16} intersections in each half of the half-plane not containing the solution. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Is the observed implementation constitutive, optional, or merely common?

T4 — Scope versus overextension. We consider the points in the quadrant not contained in a half-plane containing the solution. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Can every claimed application fill the same typed roles without metaphor?

T5 — Transfer versus domain accent. The line q in the direction is placed to go through an intersection such that there are \frac{n}{8} intersections in each half-plane defined by the line (median position). The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Does the receiving case instantiate Smallest-Circle Problem literally, co-instantiate 1 Center Problem, or only resemble it?

T6 — Autonomy versus reduction. It also states that performance is improved by dynamically re-ordering the points so that those that are found to be outside a circle are subsequently considered earlier, but this requires a change in the structure of the algorithm to store P as a "global". The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: What does Smallest-Circle Problem distinguish that the broader parent 1 Center Problem leaves together?

Structural–Framed Character¶

Smallest-Circle Problem is mixed or framed-leaning. Its structural side is the repeatable organization summarized by The smallest-circle problem (also known as minimum covering circle problem, bounding circle problem, least bounding circle problem, smallest enclosing circle problem) is a computational geometry problem of computing the smallest circle that contains all of a given set of points in the Euclidean plane. Its framed side is the computational geometry vocabulary that fixes the carrier, evidence, exceptions, and admissible transformations.

Evaluative weight: the identity can be stated descriptively even when applications carry practical stakes. Human-practice dependence: the source-grounded carrier determines whether the relation exists independently or is constituted by a practice. Institutional origin: disciplinary conventions stabilize the name and test. Vocabulary portability: The minimum covering circle of a set S can be determined by at most three points in S which lie on the boundary of the circle. Import versus recognition: literal transfer requires the same mechanism; shape alone is analogy.

Its portable skeleton is 1 Center Problem. Its character: a recurring specialist identity whose thin organization can be abstracted, while its operational meaning remains domain-bound.

Structural Core vs. Domain Accent¶

What is skeletal. The smallest-circle problem (also known as minimum covering circle problem, bounding circle problem, least bounding circle problem, smallest enclosing circle problem) is a computational geometry problem of computing the smallest circle that contains all of a given set of points in the Euclidean plane. The stable skeleton is the typed relation expressed in that definition and the entry's recognition and collapse tests. The source identifies these operative conditions: The line q in the direction is placed to go through an intersection such that there are \frac{n}{8} intersections in each half-plane defined by the line (median position). It also states that performance is improved by dynamically re-ordering the points so that those that are found to be outside a circle are subsequently considered earlier, but this requires a change in the structure of the algorithm to store P as a "global". It further constrains recognition and variation through: The minimum covering circle of a set S can be determined by at most three points in S which lie on the boundary of the circle. If it is determined by only two points, then the line segment joining those two points must be a diameter of the minimum circle.

What is domain-bound. computational geometry supplies the operative entities, technical vocabulary, warrants, and exceptions that make Smallest-Circle Problem literal. Its documented scope includes the condition that As a consequence of membership in this class, it was shown that the dependence on the dimension of the constant factor in the O(n) time bound, which was factorial for Seidel's method, could be reduced to subexponential. Another bounded application condition is that The solution of the subproblem is either the solution of the unconstrained problem or it is used to determine the half-plane where the unconstrained solution center is located. These are not decorative examples; they determine which carrier and evidence can fill the abstraction's roles.

Why no parent is asserted. Removing those specialist details does not currently yield one live catalog node that is a necessary genus for every instance. The entry is therefore approved as unparented rather than attached by topical resemblance. Its collapse evidence remains specific—If it is determined by three points, then the triangle consisting of those three points is not obtuse.—and future graph densification may discover a defensible relation only if it preserves that boundary.

This entry is a kind of Computational problem.

Approved unparented node. No current live node supplies a defensible necessary genus or structural prerequisite for Smallest-Circle Problem. The reviewed identity is: The smallest-circle problem (also known as minimum covering circle problem, bounding circle problem, least bounding circle problem, smallest enclosing circle problem) is a computational geometry problem of computing the smallest circle that contains all of a given set of points in the Euclidean plane. The accelerated suggestion was declined because topical or lexical similarity does not establish hierarchy; the node is admitted without a parent pending later graph densification.
Related reasoning operations. Evidence, representation, comparison, classification, transformation, or evaluation may participate in particular cases, but participation does not make any one of them a necessary parent of every instance.

Relationships to Other Abstractions¶

Current abstraction Smallest-Circle Problem Domain-specific

Parents (1) — more general patterns this builds on

Smallest-Circle Problem is a kind of Computational problem Domain-specific

The smallest-circle problem maps a finite point set to a minimum-radius enclosing circle.

Hierarchy path (1) — routes to 1 parentless root

Smallest-Circle Problem → Computational problem → Function (Mapping)

Neighborhood in Abstraction Space¶

Smallest-Circle Problem sits in a crowded region of the domain-specific corpus (37^th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Combinatorial Optimization & Discrete Structures (31 abstractions)

Nearest neighbors

Newton–Gauss line — 0.89
Filling radius — 0.88
Incidence (geometry) — 0.88
Skip list — 0.87
Tractable Problem — 0.87

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With¶

1 Center Problem. The parent omits the specialist differentia. Tell: Can the case establish The smallest-circle problem (also known as minimum covering circle problem, bounding circle problem, least bounding circle problem, smallest enclosing circle problem) is a computational geometry problem of computing the smallest circle that contains all of a given set of points in the Euclidean plane?
1-Center Problem. A single-facility minimax location problem that selects one feasible center to minimize the greatest distance or service cost from that center to any demand point. Tell: Which entry's carrier, operation, and failure condition are satisfied?
Mrs. Miniver's Problem. Place two disks of prescribed radii so their intersection lens has the same area as their symmetric difference, reducing feasible placements to an inverse circular-segment equation. Tell: Which entry's carrier, operation, and failure condition are satisfied?
Covering number. The minimum number of radius-r balls required to cover a specified subset of a metric or pseudometric space. Tell: Which entry's carrier, operation, and failure condition are satisfied?
A measurement, proxy, or consequence. Those may provide evidence without being the identity. Tell: Would Smallest-Circle Problem remain present if the detector or downstream effect changed?
A metaphorical analogue. A similar shape outside computational geometry lacks the specialist mechanism. Tell: Do the native roles transfer literally, or only the parent 1 Center Problem?

References¶

Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Smallest-circle_problem (revision 1369270113).
Preserved source candidate: http://www.inf.ethz.ch/personal/emo/PublFiles/SubexLinProg_ALG16_96.pdf
Preserved source candidate: http://www.inf.ethz.ch/personal/gaertner/miniball.html
Preserved source candidate: http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Bounding_volumes/Chapter_main.html
Preserved source candidate: https://github.com/hbf/miniball

The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.