Parametric search made practical

In this paper we show that in sorting-based applications of parametric search, Quicksort can replace the parallel sorting algorithms that are usually advocated. Because of the simplicity of Quicksort, this may lead to applications of parametric search that are not only efficient in theory, but in practice as well. Also, we argue that Cole's optimization of certain parametric-search algorithms may be unnecessary under realistic assumptions about the input. Furthermore, we present a generic, flexible, and easy-to-use framework that greatly simplifies the implementation of algorithms based on parametric search. We use our framework to implement an algorithm that solves the Frechet-distance problem. The implementation based on parametric search is faster than the binary-search approach that is often suggested as a practical replacement for the parametric-search technique. (C) 2004 Elsevier B.V. All rights reserved.