Optimal slope selection via cuttings

Hervé Brönnimann, Bernard Chazelle

Research output: Contribution to journalArticlepeer-review

33 Scopus citations


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 languageEnglish (US)
Pages (from-to)23-29
Number of pages7
JournalComputational Geometry: Theory and Applications
Issue number1
StatePublished - Apr 1998

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics


  • Arrangements
  • Deterministic optimal algorithm
  • Sorting


Dive into the research topics of 'Optimal slope selection via cuttings'. Together they form a unique fingerprint.

Cite this