Computing bounding polytopes of a compact set and related problems in n-dimensional space. (April 2019)

• Record Type: Journal Article
• Authors: Zheng, Yu
• Is Part Of: Computer aided design. Volume 109(2019)
• Page Start: 22
• Page End: 32
• Publication Date: 2019-04
• Subjects: Polytope -- Maximum distance -- Diameter -- Compact set -- Computational geometry; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2018.12.002
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: This paper first presents an algorithm to compute bounding polytopes of a compact set in arbitrary dimensions. Different from most of the existing work that deals with a finite point set, the compact set handled in this paper can also be an infinite set described by continuous parametric functions. Starting with any bounding polytope of the compact set, the proposed algorithm iteratively finds a sequence of cutting hyperplanes to truncate the polytope and gradually reduce its volume. As a result, a tight bounding polytope of the compact set can be computed and its tightness is controlled by a user-specified tolerance for terminating the iteration. While the algorithm keeps iterating, the polytope can get arbitrarily close to the convex hull of the compact set. Furthermore, the proposed algorithm is extended to computing the maximum distance between compact sets and the diameter of a compact set. Finally, numerical examples show that the proposed algorithms possess linear time complexity with the number of iterations. Highlights: Efficient algorithm is proposed to compute tight bounding polytopes of compact sets. A sequence of hyperplanes are computed to cut a bounding polytope of a compact set The algorithm is extended to the maximum distance and the diameter of compact sets Compact sets can be infinite and described by parametric functions in any dimension The proposed algorithms have linear time complexity with the number of iterations