Querying simplexes in quasi-triangulation

Deok-Soo Kim, Jae Kwan Kim, Youngsong Cho, Chong Min Kim

Research output: Contribution to journalArticle

13 Citations (Scopus)

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 β-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 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.

Original languageEnglish
Pages (from-to)85-98
Number of pages14
JournalCAD Computer Aided Design
Volume44
Issue number2
DOIs
StatePublished - 2012 Feb 1

Fingerprint

Triangulation
Molecules
Data structures
Scanning

Keywords

  • Beta-complex
  • Beta-shape
  • Orthogonal range search
  • Particle proximity
  • Quasi-triangulation
  • Simplex query
  • Voronoi diagram of spheres

Cite this

Kim, Deok-Soo ; Kim, Jae Kwan ; Cho, Youngsong ; Kim, Chong Min. / Querying simplexes in quasi-triangulation. In: CAD Computer Aided Design. 2012 ; Vol. 44, No. 2. pp. 85-98.
@article{21189e33651142e791fffd7c451b68dd,
title = "Querying simplexes in quasi-triangulation",
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 β-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 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.",
keywords = "Beta-complex, Beta-shape, Orthogonal range search, Particle proximity, Quasi-triangulation, Simplex query, Voronoi diagram of spheres",
author = "Deok-Soo Kim and Kim, {Jae Kwan} and Youngsong Cho and Kim, {Chong Min}",
year = "2012",
month = "2",
day = "1",
doi = "10.1016/j.cad.2011.09.010",
language = "English",
volume = "44",
pages = "85--98",
journal = "CAD Computer Aided Design",
issn = "0010-4485",
number = "2",

}

Querying simplexes in quasi-triangulation. / Kim, Deok-Soo; Kim, Jae Kwan; Cho, Youngsong; Kim, Chong Min.

In: CAD Computer Aided Design, Vol. 44, No. 2, 01.02.2012, p. 85-98.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Querying simplexes in quasi-triangulation

AU - Kim, Deok-Soo

AU - Kim, Jae Kwan

AU - Cho, Youngsong

AU - Kim, Chong Min

PY - 2012/2/1

Y1 - 2012/2/1

N2 - 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 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.

AB - 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 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.

KW - Beta-complex

KW - Beta-shape

KW - Orthogonal range search

KW - Particle proximity

KW - Quasi-triangulation

KW - Simplex query

KW - Voronoi diagram of spheres

UR - http://www.scopus.com/inward/record.url?scp=81855199036&partnerID=8YFLogxK

U2 - 10.1016/j.cad.2011.09.010

DO - 10.1016/j.cad.2011.09.010

M3 - Article

AN - SCOPUS:81855199036

VL - 44

SP - 85

EP - 98

JO - CAD Computer Aided Design

JF - CAD Computer Aided Design

SN - 0010-4485

IS - 2

ER -