Accession Number:

ADA011024

Title:

Convex Hulls of Finite Planar and Spatial Sets of Points.

Descriptive Note:

Technical rept.,

Corporate Author:

ILLINOIS UNIV URBANA COORDINATED SCIENCE LAB

Personal Author(s):

Report Date:

1975-04-01

Pagination or Media Count:

25.0

Abstract:

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.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE