User:Apizzimenti/sandbox/Smallest Enclosing Disk – Draft

Megiddo's Algorithm

Megiddo's solution is a recursive algorithm which uses a prune and search technique: by procedurally removing ("pruning") infeasible solutions from the search tree,

Megiddo's algorithm

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

Megiddo's algorithm is based on the technique called prune and search reducing size of the problem by removal of n/16 of unnecessary points.

That leads to the recurrence t(n)≤ t(15n/16)+cn giving t(n)=16cn.

The algorithm is rather complicated and it is reflected in big multiplicative constant. The reduction needs to solve twice the similar problem where center of the sought-after enclosing circle is constrained to lie on a given line. The solution of the subproblem is either solution of unconstrained problem or it is used to determine the half-plane where the unconstrained solution center is located.

The n/16 points to be discarded are found the following way: Points P_i are arranged to pairs what defines 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 -$\infty$ or +$\infty$ according our needs.) Let Q_k be 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 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 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 n/4 points leading to recurrence t(n)≤ t(3n/4)+cn giving t(n)=4cn.

The 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.)

| last = Megiddo | first = Nimrod | authorlink = Nimrod Megiddo

| doi = 10.1137/0212052
| issue = 4
| journal = SIAM Journal on Computing
| mr = 721011
| pages = 759–776
| title = Linear-time algorithms for linear programming in R3 and related problems
| volume = 12
| year = 1983}}.