Convex Hulls of Finite Planar and Spatial Sets of Points.

Abstract

The convex hulls of planar and spatial sets of n points can be determined with O(n 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 O(n lg n) operations, so that the time complexity of the proposed algorithms is optimal within a multiplicative constant.

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1975
Accession Number
ADA011024

Entities

People

  • F. P. Preparta
  • S. J. Hong

Organizations

  • University of Illinois Urbana–Champaign

Tags

DTIC Thesaurus Topics

  • Algorithms

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Graph Algorithms and Convex Optimization.