### Abstract

Consider n independent identically distributed random vectors from R^{d} 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 R^{2}.

Original language | English (US) |
---|---|

Pages (from-to) | 361-366 |

Number of pages | 6 |

Journal | Computing |

Volume | 26 |

Issue number | 4 |

DOIs | |

State | Published - 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

Devroye, L., & Toussaint, G. T. (1981). A note on linear expected time algorithms for finding convex hulls.

*Computing*,*26*(4), 361-366. https://doi.org/10.1007/BF02237955