Real-time approximation of molecular interaction interfaces based on hierarchical space decomposition

Joon Kyung Seong, Nakhoon Baek, Ku Jin Kim

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


The interaction interface between two molecules can be represented as a bisector surface equidistant from the two sets of spheres of varying radii representing atoms. We recursively divide a box containing both sphere-sets into uniform pairs of sub-boxes. The distance from each new box to each sphere-set is conservatively approximated by an interval, and the number of sphere-box computations is greatly reduced by pre-partitioning each sphere-set using a kd-tree. The subdivision terminates at a specified resolution, creating a box partition (BP) tree. A piecewise linear approximation of the bisector surface is then obtained by traversing the leaves of the BP tree and connecting points equidistant from the sphere-sets. In 124 experiments with up to 16,728 spheres, a bisector surface with a resolution of 124 of the original bounding box was obtained in 28.8 ms on average.

Original languageEnglish
Pages (from-to)1598-1605
Number of pages8
JournalCAD Computer Aided Design
Issue number12
Publication statusPublished - 2011 Dec
Externally publishedYes

Bibliographical note

Funding Information:
This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology ( 2010-0007785 and 2010-0028106 ) and the Korea Science and Engineering Foundation (KOSEF) grant funded by the Korean government (MEST) ( 2010-0015879 ).


  • Bisector
  • Interaction interface
  • Molecular docking
  • Molecule assembly
  • Space-partitioning structure
  • kd-tree

ASJC Scopus subject areas

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Industrial and Manufacturing Engineering


Dive into the research topics of 'Real-time approximation of molecular interaction interfaces based on hierarchical space decomposition'. Together they form a unique fingerprint.

Cite this