A new representation and algorithm for constructing convex hulls in higher dimensional spaces
| Autor: | Nelson Acosta, M. Carolina Tommasi, Marcelo Alejandro Tosini, Martín F. Mezzanotte |
|---|---|
| Rok vydání: | 1992 |
| Předmět: |
Convex hull
Mathematical optimization Computer science Convex set Proper convex function Subderivative Krein–Milman theorem Choquet theory Theoretical Computer Science Convex polytope Convex combination Convex conjugate Absolutely convex set Finite set Orthogonal convex hull Convex analysis Linear matrix inequality Computer Science Applications Computational Theory and Mathematics Hardware and Architecture Convex optimization Tight span Convex body Output-sensitive algorithm Voronoi diagram Gift wrapping algorithm Software Alpha shape |
| Zdroj: | Journal of Computer Science and Technology. 7:1-5 |
| ISSN: | 1860-4749 1000-9000 |
| DOI: | 10.1007/bf02946159 |
| Popis: | This paper presents a new and simple scheme to describe the convex hull in Rd, which only uses three kinds of the faces of the convex hull, i. e., thed-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 algorithm is optimal in the worst case for evend. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink