Abstract | ||
---|---|---|
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 @b-complex and the @b-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 kd-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. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1016/j.cad.2011.09.010 | Computer-Aided Design |
Keywords | Field | DocType |
kd-tree data structure suit,high-level query operator,incremental query,simplex query problem,observations facilitates efficient simplex,efficient query algorithm,querying simplex,efficient performance,three-dimensional space,spatial structure,dual structure | Discrete mathematics,Data structure,Mathematical optimization,Algorithm,Simplex,Operator (computer programming),Voronoi diagram,Search problem,Quasi-triangulation,Mathematics,Delaunay triangulation,Bounding overwatch | Journal |
Volume | Issue | ISSN |
44 | 2 | 0010-4485 |
Citations | PageRank | References |
9 | 0.58 | 17 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Deok-Soo Kim | 1 | 633 | 59.12 |
Jaekwan Kim | 2 | 55 | 5.70 |
Youngsong Cho | 3 | 250 | 22.15 |
Chong-Min Kim | 4 | 9 | 0.58 |