Accession Number : ADA113420

Title :   Finding the Convex Hull of a Simple Polygon,

Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Graham,Rondld L ; Yao,Frances

PDF Url : ADA113420

Report Date : Nov 1981

Pagination or Media Count : 10

Abstract : It is well known that the convex hull of a set of n points in the (Euclidean) plane can be found by an algorithm having worst-case complexity O(n log n). In this note we give a short linear algorithm for finding the convex hull in the case that the (ordered) set of points from the vertices of a simple (i.e., non-self-intersecting) polygon. (Author)

Descriptors :   *Convex sets, *Polygons, Algorithms, Computer graphics

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE