How Similar Are Quasi-, Regular, and Delaunay Triangulations in R~3?

摘要

Voronoi diagrams and quasi-triangulations are powerful for solving spatial problems among spherical particles with different radii. However, a quasi-triangulation can be a non-simplicial complex due to anomaly conditions. While quasi-triangulation is straightforward to use when it is a simplicial complex, it may not seem so if it is not. In this paper, we report the experimental statistics of showing the phenomena related with two fundamental issues: i) How frequently anomalies occur in the quasi-triangulation of the arrangement of spherical atoms in R~3 and ii) how much similar or dissimilar the three related structures (i.e., the quasi-triangulation, the regular triangulation, and the Delaunay tri-angulation of an atomic arrangements) are. The observations from the experiments are as follows: i) Anomalies occur extremely rarely in molecular structures and occur very rarely even in random sphere sets, and ii) the three dual structures of a given set of spheres are not similar.