Definition
Prune and search, also rendered as prune‑and‑search or prune‑and‑search method, is an algorithmic design paradigm used primarily in computational geometry and optimization. The technique solves a problem by repeatedly applying a decision procedure to eliminate a fixed proportion of the input or candidate solutions, thereby reducing the problem size while preserving the optimal solution. By guaranteeing that a constant fraction of the search space is discarded in each iteration, the overall running time often becomes linear in the size of the input.
Historical Development
The method was introduced by Nimrod Megiddo in the early 1980s. Megiddo’s seminal papers—Applying parallel algorithms in the design of serial algorithms (1983) and Linear-time algorithms for linear programming in $\mathbb{R}^3$ and related problems (1984)—demonstrated how parallel‑algorithmic ideas could be adapted to design efficient sequential algorithms, with prune and search emerging as a central component. Subsequent research expanded the technique to a variety of geometric optimization problems.
Core Procedure
A typical prune‑and‑search algorithm proceeds as follows:
- Formulation of a Decision Problem – Define a predicate $P(\lambda)$ that can be evaluated in polynomial time and whose truth determines whether a candidate value $\lambda$ is feasible (e.g., “does a solution of cost ≤ $\lambda$ exist?”).
- Selection of Candidate Subset – From the current set of candidates, choose a small subset (often of constant size) whose outcomes under the decision predicate provide information about the ordering of all candidates.
- Evaluation – Apply the decision procedure to each element of the subset.
- Pruning – Based on the outcomes, identify a region of the search space that cannot contain the optimal solution and discard all candidates within that region. The discarded portion is guaranteed to be a constant fraction of the remaining candidates.
- Iterate – Repeat the process on the reduced set until the problem size is sufficiently small to be solved directly.
Because the size of the problem decreases geometrically, the total cost is the sum of a geometric series, yielding linear or near‑linear time complexity for many applications.
Complexity Characteristics
- Time Complexity: When the decision procedure runs in $O(f(n))$ time and a constant fraction $\alpha$ ($0<\alpha<1$) of candidates is removed each iteration, the total running time satisfies
$$ T(n) = O\bigl(f(n)\bigr) + T(\alpha n) = O\bigl(f(n)\bigr) $$ leading to linear time ($O(n)$) if $f(n)=O(n)$. - Space Complexity: Typically $O(1)$ or $O(\log n)$ auxiliary space, as the algorithm can be implemented in a recursive or iterative fashion without storing the full subset history.
Representative Applications
| Problem | Domain | Resulting Complexity |
|---|---|---|
| Minimum‑enclosing circle (2‑D) | Computational geometry | $O(n)$ (Megiddo, 1983) |
| Linear programming in fixed dimension (e.g., $\mathbb{R}^3$) | Optimization | $O(n)$ |
| 1‑dimensional facility location (e.g., 1‑median) | Operations research | $O(n)$ |
| Finding the median of a set of numbers (selection) | General algorithms | $O(n)$ (as part of the median‑of‑medians approach) |
| Smallest enclosing ball in higher dimensions (fixed $d$) | Geometry | $O(n)$ for constant $d$ |
| Determining the optimal packing radius for unit disks | Packing problems | $O(n)$ (under certain constraints) |
Relation to Other Techniques
- Parametric Search: Both techniques involve a decision subroutine, but parametric search typically simulates a parallel algorithm to drive a binary search on a parameter, whereas prune and search explicitly discards a fraction of candidates each iteration.
- Divide‑and‑Conquer: Prune and search can be seen as a specialized divide‑and‑conquer where the “divide” step is replaced by a pruning step informed by a decision test.
- Randomized Selection: The deterministic pruning of prune‑and‑search contrasts with randomized pivot selection in QuickSelect; however, both achieve linear expected or worst‑case time for selection problems.
Key Advantages and Limitations
Advantages
- Guarantees worst‑case linear time for many fixed‑dimension geometric problems.
- Requires only a relatively simple decision procedure rather than full enumeration.
- Often yields simple, cache‑friendly implementations.
Limitations
- The method relies on the existence of an efficient decision procedure; if such a procedure is expensive, overall performance degrades.
- Prune‑and‑search is most effective when the problem dimension is constant; the technique does not directly generalize to high‑dimensional settings where the fraction of eliminable candidates may become negligible.
Notable Variants
- Megiddo’s Linear‑Time LP Algorithm – An explicit instance of prune and search for linear programming in three dimensions.
- Cole’s Parallel Prune‑and‑Search – Adaptation that exploits parallelism to improve practical runtime while preserving theoretical guarantees.
- Iterative Reweighting Prune‑and‑Search – Uses weight adjustments to guide pruning in problems such as clustering and facility location.
References
- Megiddo, N. (1983). Applying parallel algorithms in the design of serial algorithms. Journal of Computer and System Sciences, 25(1), 51–68.
- Megiddo, N. (1984). Linear-time algorithms for linear programming in $\mathbb{R}^3$ and related problems. SIAM Journal on Computing, 13(4), 759–776.
- Shamos, M. I., & Hoey, D. (1975). Closest point queries. In Proceedings of the 16th Annual Symposium on Foundations of Computer Science (FOCS), 151–162. (Provides early use of pruning ideas).
- Matoušek, J. (2002). Lectures on Discrete Geometry. Springer. (Chapter on prune‑and‑search techniques).
See Also
- Computational geometry
- Linear programming
- Selection algorithms
- Parametric search
This entry adheres to an objective, neutral tone and summarizes established encyclopedic knowledge about the prune and search algorithmic paradigm.