A note on linear expected time algorithms for finding convex hulls

L. Devroye, G. T. Toussaint

Research output: Contribution to journalArticle

Abstract

Consider n independent identically distributed random vectors from Rd with common density f, and let E (C) be the average complexity of an algorithm that finds the convex hull of these points. Most well-known algorithms satisfy E (C)=0(n) for certain classes of densities. In this note, we show that E (C)=0(n) for algorithms that use a "throw-away" pre-processing step when f is bounded away from 0 and ∞ on any nondegenerate rectangle of R2.

Original languageEnglish (US)
Pages (from-to)361-366
Number of pages6
JournalComputing
Volume26
Issue number4
DOIs
StatePublished - Dec 1981

Keywords

  • Convex hull
  • algorithms
  • average complexity
  • geometrical complexity

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Numerical Analysis
  • Computer Science Applications
  • Computational Theory and Mathematics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'A note on linear expected time algorithms for finding convex hulls'. Together they form a unique fingerprint.

  • Cite this