Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 23-29 |
Number of pages | 7 |
Journal | Computational Geometry: Theory and Applications |
Volume | 10 |
Issue number | 1 |
DOIs | |
State | Published - Apr 1998 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Computer Science Applications
- Geometry and Topology
- Control and Optimization
- Computational Theory and Mathematics
- Computational Mathematics
Keywords
- Arrangements
- Deterministic optimal algorithm
- Sorting