Convex Hulls of Finite Planar and Spatial Sets of Points.
ILLINOIS UNIV URBANA COORDINATED SCIENCE LAB
Pagination or Media Count:
The convex hulls of planar and spatial sets of n points can be determined with On lg n operations. The presented algorithms use the divide and conquer technique and recursively apply a merge procedure for two nonintersecting convex hulls. It is also shown that any convex hull algorithm requires at least On lg n operations, so that the time complexity of the proposed algorithms is optimal within a multiplicative constant.
- Theoretical Mathematics