Searching Simplexes in Quasi-triangulation

Given a quasi-triangulation of a molecule, searching the simplexes of a particular bounding state for the spherical probe of a given radius occurs frequently. While such simplexes can be found by linearly scanning all simplexes in the quasi-triangulation, it is desirable to do the search faster. This paper presents an algorithm for searching simplexes quickly using the kd-tree data structure. The approach is based on the transformation of the simplex search problem in the R³ space to the orthogonal range search problem of points in another R³ space.