Optimal slope selection via cuttings

Hervé Brönnimann, Bernard Chazelle

Research output: Contribution to journalArticle

28 Scopus citations

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

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

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

  • Cite this