Manifoldization of ββ-shapes in O(n)O(n) time

The ββ-shape and the ββ-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 ββ-shape is inconvenient for reasoning about the surface structure of a sphere set. In this paper, we present an algorithm to transform a ββ-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 ββ-shape, the algorithm augments the ββ-complex which corresponds to the ββ-shape so that all the non-manifoldness is resolved on such simplexes. The algorithm runs in O(n)O(n) time, without any floating-point operation, in the worst case for protein models where nn is the number of spherical atoms. We also provide some experimental results obtained from real protein models available from the Protein Data Bank.