Abstract
We present simple output-sensitive algorithms that construct the convex hull of a set of n points in two or three dimensions in worst-case optimal O(n log h) time and O(n) space, where h denotes the number of vertices of the convex hull.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 361-368 |
| Number of pages | 8 |
| Journal | Discrete and Computational Geometry |
| Volume | 16 |
| Issue number | 4 |
| DOIs | |
| State | Published - Dec 1996 |
| Externally published | Yes |
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics