## Abstract

Kirkpatrick and Seidel [13,14] recently proposed an algorithm for computing the convex hull of n points in the plane that runs in O(n log h) worst case time, where h denotes the number of points on the convex hull of the set. Here a modification of their algorithm is proposed that is believed to run in O(n) expected time for many reasonable distributions of points. The above O(n log h) algorithmsare experimentally compared to the O(n log n) 'throw-away' algorithms of Akl, Devroye and Toussaint [2, 8, 20]. The results suggest that although the O(n Log h) algorithms may be the 'ultimate' ones in theory, they are of little practical value from the point of view of running time.

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

Pages (from-to) | 29-34 |

Number of pages | 6 |

Journal | Pattern Recognition Letters |

Volume | 3 |

Issue number | 1 |

DOIs | |

State | Published - Jan 1985 |

## Keywords

- Convex hull
- algorithms
- complexity
- computational geometry

## ASJC Scopus subject areas

- Software
- Signal Processing
- Computer Vision and Pattern Recognition
- Artificial Intelligence