Smallest-circle problem

Run of Megiddo's algorithm phase, discarding from point set A, B, ..., U needless points E, T.

Megiddo's algorithm[9] is based on the technique called prune and search, reducing the size of the problem by removing ${\textstyle {\frac {n}{16}}}$ unnecessary points. That leads to the recurrence ${\displaystyle t(n)\leq t\left({\frac {15n}{16}}\right)+cn}$ giving ${\displaystyle t(n)=16cn}$.

The algorithm is rather complicated and it is reflected by its big multiplicative constant. The reduction needs to solve twice the similar problem where the center of the sought-after enclosing circle is constrained to lie on a given line. 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.

The ${\textstyle {\frac {n}{16}}}$ points to be discarded are found as follows: The points P_i are arranged into pairs which defines ${\textstyle {\frac {n}{2}}}$ lines p_j as their bisectors. The median average p_m of bisectors in order by their directions (oriented to the same half-plane determined by bisector p₁) is found and pairs of bisectors are made, such that in each pair one bisector has direction at most p_m and the other at least p_m (direction p₁ could be considered as −${\displaystyle \infty }$ or +${\displaystyle \infty }$ according our needs.) Let Q_k be the intersection of the bisectors in the k-th pair.

The line q in the p₁ direction is placed to go through an intersection Q_x such that there are ${\textstyle {\frac {n}{8}}}$ intersections in each half-plane defined by the line (median position). The constrained version of the enclosing problem is run on the line q' which determines half-plane where the center is located. The line q′ in the p_m direction is placed to go through an intersection Q_x' such that there are ${\textstyle {\frac {n}{16}}}$ intersections in each half of the half-plane not containing the solution. The constrained version of the enclosing problem is run on line q′ which together with q determines the quadrant where the center is located. We consider the points Q_k in the quadrant not contained in a half-plane containing the solution. One of the bisectors of the pair defining Q_k has the direction ensuring which of points P_i defining the bisector is closer to each point in the quadrant containing the center of the enclosing circle. This point could be discarded.

The constrained version of the algorithm is also solved by the prune and search technique, but reducing the problem size by removal of ${\textstyle {\frac {n}{4}}}$ points leading to recurrence

${\displaystyle t(n)\leq t\left({\frac {3n}{4}}\right)+cn}$

giving ${\displaystyle t(n)=4cn}$.

The ${\textstyle {\frac {n}{4}}}$ points to be discarded are found as follows: Points P_i are arranged into pairs. For each pair, the intersection Q_j of its bisector with the constraining line q is found (If this intersection does not exist we could remove one point from the pair immediately). The median M of points Q_j on the line q is found and in O(n) time is determined which halfline of q starting in M contains the solution of the constrained problem. We consider points Q_j from the other half. We know which of the points P_i defining Q_j is closer to the each point of the halfline containing center of the enclosing circle of the constrained problem solution. This point could be discarded.

The half-plane where the unconstrained solution lies could be determined by the points P_i on the boundary of the constrained circle solution. (The first and last point on the circle in each half-plane suffice. If the center belongs to their convex hull, it is unconstrained solution, otherwise the direction to the nearest edge determines the half-plane of the unconstrained solution.)

The algorithm is recursive.

The initial input is a set P of points. The algorithm selects one point p randomly and uniformly from P, and recursively finds the minimal circle containing P – {p}, i.e. all of the other points in P except p. If the returned circle also encloses p, it is the minimal circle for the whole of P and is returned.

Otherwise, point p must lie on the boundary of the result circle. It recurses, but with the set R of points known to be on the boundary as an additional parameter.

The recursion terminates when P is empty, and a solution can be found from the points in R: for 0 or 1 points the solution is trivial, for 2 points the minimal circle has its center at the midpoint between the two points, and for 3 points the circle is the circumcircle of the triangle described by the points. (In three dimensions, 4 points require the calculation of the circumsphere of a tetrahedron.)

Recursion can also terminate when R has size 3 (in 2D, or 4 in 3D) because the remaining points in P must lie within the circle described by R.

algorithm welzl is[8]
    input: Finite sets P and R of points in the plane |R| ≤ 3.
    output: Minimal disk enclosing P with R on the boundary.

    if P is empty or |R| = 3 then
        return trivial(R)
    choose p in P (randomly and uniformly)
    D := welzl(P − {p}, R)
    if p is in D then
        return D

    return welzl(P − {p}, R ∪ {p})

Welzl's paper states that it is sufficient to randomly permute the input at the start, rather than performing independently random choices of p on each recursion.

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".