Manifoldization of beta-shapes in O(n) time

作者：Kim Deok Soo^*; Lee Changhee; Cho Youngsong; Kim Donguk

来源：Computer-Aided Design, 2010, 42(4): 322-339.

DOI：10.1016/j.cad.2009.12.005

• beta-shape
• beta-complex
• Voronoi diagram of spheres
• Quasi-triangulation
• Topology
• Mesh
• Non-manifold
• Protein structure

The beta-shape and the beta-complex are recently announced geometric constructs which facilitate efficient reasoning about the proximity among spherical particles in three-dimensional space. They have proven to be very useful for the structural analysis of bio-molecules such as proteins. Being non-manifold, however, the topology traversal on the boundary of the beta-shape is inconvenient for reasoning about the surface structure of a sphere set. In this paper, we present an algorithm to transform a beta-shape from being non-manifold to manifold without altering any of the geometric characteristics of the model. After locating the simplexes where the non-manifoldness is defined on the beta-shape, the algorithm augments the beta-complex which corresponds to the beta-shape so that all the non-manifoldness is resolved on such simplexes. The algorithm runs in O(n) time, without any floating-point operation, in the worst case for protein models where n is the number of spherical atoms. We also provide some experimental results obtained from real protein models available from the Protein Data Bank.

• 出版日期2010-4