\input zb-basic
\input zb-ioport
\iteman{io-port 05861702}
\itemau{Kim, Deok-Soo; Lee, Changhee; Cho, Youngsong; Kim, Donguk}
\itemti{Manifoldization of $\beta $-shapes in $O(n)$ time.}
\itemso{Comput.-Aided Des. 42, No. 4, 322-339 (2010).}
\itemab
Summary: 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.
\itemrv{~}
\itemcc{}
\itemut{$\beta $-shape; $\beta $-complex; Voronoi diagram of spheres; quasi-triangulation; topology; mesh; non-manifold; protein structure}
\itemli{doi:10.1016/j.cad.2009.12.005}
\end