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({\frac {15n}{16}})+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 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 the following way: Points P_i are arranged to pairs what defines ${\textstyle {\frac {n}{2}}}$ lines p_j as their bisectors. Median p_m of bisectors in order by their directions (oriented to the same half-plane determined by bisector p₁) is found and pairs from 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 bisectors of k-th pair.

Line q in the p₁ direction is placed to go through an intersection Q_x such that there is ${\textstyle {\frac {n}{8}}}$ intersections in each half-plane defined by the line (median position). Constrained version of the enclosing problem is run on line q what determines half-plane where the center is located. Line q' in the p_m direction is placed to go through an intersection Q_x' such that there is ${\textstyle {\frac {n}{16}}}$ intersections in each half of the half-plane not containing the solution. Constrained version of the enclosing problem is run on line q' what together with q determines quadrant, where the center is located. We consider the points Q_k in the quadrant not contained in a half-plane containing solution. One of the bisectors of 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 problem size by removal of ${\textstyle {\frac {n}{4}}}$ points leading to recurrence ${\displaystyle t(n)\leq t({\frac {3n}{4}})+cn}$ giving ${\displaystyle t(n)=4cn}$.

The ${\textstyle {\frac {n}{4}}}$ points to be discarded are found the following way: Points P_i are arranged to pairs. For each pair intersection Q_j of its bisector with the constraining line q is found (If intersection does not exist we could remove one point from the pair immediately). 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 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. (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 direction to the nearest edge determines 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 as an additional parameter the set R of points known to be on the boundary.

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 centre 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 terahedron.)

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