The quasi-triangulation and the beta-complex: theory and applications

The Voronoi/Delaunay structures are everywhere in nature and useful for understanding the spatial structure of a point set. Being powerful computational tools, their generalization has been made in various directions including the Voronoi diagram of spherical balls. The Voronoi diagram of spherical balls nicely defines the proximity among the balls where the Euclidean distance is used from the spherical boundary of balls. Like its counterparts of the ordinary Voronoi diagram of points or the power diagram, the dual structure can be more convenient in both representing and traversing the topology structure of the Voronoi diagram. However, unlike the Delaunay triangulation and the regular triangulation, the dual structure of the Voronoi diagram of balls, the quasi-triangulation, is not a simplicial complex and creates a number of anomaly cases which cause difficulties in the representation and traversal of topology.
This talk will introduce the Voronoi diagram of balls and its quasi-triangulation, particularly in the three-dimensional space. Given its definition, the properties of the quasi-triangulation, including the anomalies, will be presented with the underlying data structure to store its topology. Based on the quasi-triangulation, we define a new geometric structure called the beta-complex which concisely yet efficiently represents the proximity among all spherical balls within the boundary of the input ball set, where its boundary is appropriately defined. It turns out that thus defined the beta-complex can be used to efficiently solve geometry and topology problems for the ball set. Among many potential application areas, the structural molecular biology is the utmost application area because the beta-complex immediately and efficiently solves many geometry problems related to important structural molecular biology problems: Examples include the computation of the molecular surface, the extraction of pockets on the boundary of molecule, the computation of areas of various types of surfaces defined on a molecule, the computation of various kinds of volumes defined on a molecule, the docking simulation, etc. We will also demonstrate our molecular modeling and analysis software, BetaMol, which is entirely based on the unified, single representation of the quasi-triangulation and the beta-complex.