

International conference "GEOMETRY, TOPOLOGY, ALGEBRA and NUMBER THEORY, APPLICATIONS" dedicated to the 120th anniversary of Boris Delone (1890–1980)
August 18, 2010 11:10, Moscow






The quasitriangulation and the betacomplex: theory and applications
Kim DeokSoo^{} 
Number of views: 
This page:  302  Video files:  92 

Abstract:
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 quasitriangulation, 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 quasitriangulation, particularly in the threedimensional space. Given its definition, the properties of the quasitriangulation, including the anomalies, will be presented with the underlying data structure to store its topology. Based on the quasitriangulation, we define a new geometric structure called the betacomplex 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 betacomplex 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 betacomplex 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 quasitriangulation and the betacomplex.
Language: English

