Three-dimensional beta-shapes and beta-complexes via quasi-triangulation

The proximity and topology among particles are often the most important factor for understanding the spatial structure of particles. Reasoning the morphological structure of molecules and reconstructing a surface from a point set are examples where proximity among particles is important. Traditionally, the Voronoi diagram of points, the power diagram, the Delaunay triangulation, and the regular triangulation, etc. have been used for understanding proximity among particles. In this paper, we present the theory of the ββ-shape and the ββ-complex and the corresponding algorithms for reasoning proximity among a set of spherical particles, both using the quasi-triangulation which is the dual of the Voronoi diagram of spheres. Given the Voronoi diagram of spheres, we first transform the Voronoi diagram to the quasi-triangulation. Then, we compute some intervals called ββ-intervals for the singular, regular, and interior states of each simplex in the quasi-triangulation. From the sorted set of simplexes, the ββ-shape and the ββ-complex corresponding to a particular value of ββ can be found efficiently. Given the Voronoi diagram of spheres, the quasi-triangulation can be obtained in O(m)O(m) time in the worst case, where mm represents the number of simplexes in the quasi-triangulation. Then, the ββ-intervals for all simplexes in the quasi-triangulation can also be computed in O(m)O(m) time in the worst case. After sorting the simplexes using the low bound values of the ββ-intervals of each simplex in O(mlogm)O(mlogm) time, the ββ-shape and the ββ-complex can be computed in O(logm+k)(logm+k) time in the worst case by a binary search followed by a sequential search in the neighborhood, where kk represents the number of simplexes in the ββ-shape or the ββ-complex. The presented theory of the ββ-shape and the ββ-complex will be equally useful for diverse areas such as structural biology, computer graphics, geometric modelling, computational geometry, CAD, physics, and chemistry, where the core hurdle lies in determining the proximity among spherical particles.

Research highlights► Theory and algorithms of the beta-shape and beta-complex for spheres are presented. ► Beta-shape and beta-complex can be computed efficiently. ► Beta-shape and beta-complex will be useful for diverse areas, in particular for structural molecular biology.