Prune and search
The basic idea of the method is a recursive procedure in which at each step the input size is reduced ("pruned") by a constant factor 0 < p < 1. As such, it is a form of decrease and conquer algorithm, where at each step the decrease is by a constant factor. Let n be the input size, T(n) be the time complexity of the whole prune-and-search algorithm, S(n) is the time complexity of the pruning step, then T(n) obeys the following recurrence relation:
In particular, Megiddo himself used this approach in his linear time algorithm for the linear programming problem when the dimension is fixed and for the minimal enclosing sphere problem for a set of points in space.
- N. Megiddo. Linear-time algorithms for linear programming in R3 and related problems. SIAM J. Computing, 12:759–776, 1983.
- Nimrod Megiddo, Linear Programming in Linear Time When the Dimension Is Fixed, 1984