Querying simplexes in quasi-triangulation

Given a quasi-triangulation, the dual structure of the Voronoi diagram of a molecule, querying its simplexes of a particular bounding state for the spherical probe of a given radius occurs frequently. The ββ-complex and the ββ-shape are such examples with various applications for reasoning the spatial structure of molecules. While such simplexes can be found by linearly scanning all simplexes in the quasi-triangulation, it is desirable to do the query faster. This paper introduces the Q2P-transformation that transforms the simplex query problem in the three-dimensional space to the orthogonal range search problem of points in another three-dimensional space. Based on this observation, we show that the kdkd-tree data structure suits very well for developing efficient query algorithms for the quasi-triangulation of molecules using the set of sixteen primitive and the set of ten high-level query operators. In particular, the proposed method shows an extremely efficient performance for incremental queries. A subset of the presented observations facilitates efficient simplex queries for any simplicial complexes including the Delaunay and regular triangulations.

► A simplex query is important for solving structural molecular biology problems.
► Q2P-transformation reduces the problem to the orthogonal range search problem.
► Q2P-transformation is particularly useful for an incremental query.
► There are sixteen primitive- and ten high-level query operators.
► Kd-tree is an appropriate data structure for the Q2P-transformation.