| A New Representation and Algorithm for Constructing Convex Hulls in Higher Dim ensional Spaces |
| |
| 引用本文： | L Wei,Liang Youdong. A New Representation and Algorithm for Constructing Convex Hulls in Higher Dim ensional Spaces[J]. 计算机科学技术学报, 1992, 7(1): 1-5. DOI: 10.1007/BF02946159 |
| |
| 作者姓名： | L Wei Liang Youdong |
| |
| 作者单位： | [1]CAD／CAMResearchCenter,ZheijiangUniversity,Hanzhou310027 [2]CAD／CAMResearchCenter,ZheijiangUniversity,H |
| |
| 基金项目： | This work is supported by the National Natural Science Foundation of China. |
| |
| 摘 要： | 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 and 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 runniing time as well as the storage for the new algorithm is also theoretically made.The algorithm is optimal in the worst case for even d.
|
| 关 键 词： | CAD CAM 高维空间 凸包 |
A new representation and algorithm for constructing convex hulls in higher dimensional spaces |
| |
| Wei Lü,Youdong Liang. A new representation and algorithm for constructing convex hulls in higher dimensional spaces[J]. Journal of Computer Science and Technology, 1992, 7(1): 1-5. DOI: 10.1007/BF02946159 |
| |
| Authors: | Wei Lü Youdong Liang |
| |
| Affiliation: | CAD/CAM Research Center Zhejiang University; Hanzhou; CAD/CAM Research Center; Zhejiang University; |
| |
| Abstract: | 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. |
| |
| Keywords: | |
| 本文献已被 CNKI 维普 SpringerLink 等数据库收录！ |
| 点击此处可从《计算机科学技术学报》浏览原始摘要信息 |
|
点击此处可从《计算机科学技术学报》下载免费的PDF全文 |
