A New Representation and Algorithm for Constructing Convex Hulls in Higher Dim ensional Spaces

This paper presents a new and simple scheme to describe the convex hull in R~d,which only uses three kinds of the faces of the convex hull,i.e.,the d-1-faces,d-2-faces and 0-faces.Thus,we develop an efficient new algorithm for constructing the convex hull of a finite set of points incrementally. This algorithm employs much less storage and time than that of the previously-existing approaches.The analysis of the running time as well as the storage for the new algorithm is also theoretically made.The algorith…