We give an optimal deterministic O(n log n)-time algorithm for slope selection. The algorithm borrows from the optimal solution given in (Cole et al., 1989) but avoids the complicated machinery of the AKS sorting network and parametric searching. This is achieved by redesigning and refining the O(n log2 n)-time algorithm of Chazelle et al. (1993) with the help of additional approximation tools.
All Science Journal Classification (ASJC) codes
- Computer Science Applications
- Geometry and Topology
- Control and Optimization
- Computational Theory and Mathematics
- Computational Mathematics
- Deterministic optimal algorithm