US 7,679,615 B2Granted

Calculating three-dimensional (3D) Voronoi diagrams

AssigneeIucf-Hyu (Industry-University Cooperation Foundation Hanyang University)

InventorsDeok-Soo Kim, Youngsong Cho, Donguk Kim

Life of this patent

Estimating the term…

Loading patent…

Abstract

Systems and methods for computing three-dimensional (3D) Euclidean Voronoi diagrams are disclosed. For some embodiments, a set of 3D objects is accessed, in which each 3D object is mathematically defined. Thereafter, a Voronoi region associated with each of the 3D objects is computed, thereby resulting in a complete Euclidean Voronoi diagram of the set of 3D objects. In some embodiments, the 3D objects are spheres, each of which is defined by a center and a radius. For other embodiments, the 3D objects are convex objects, each of which is mathematically-definable (e.g., cylinders, sphero-cylinders, etc.). Unlike prior approaches that suggested using a numerical approach to computing the Voronoi diagram, the present disclosure employs mathematical approaches for computing the Euclidean Voronoi diagram, thereby improving efficiency in the computation of the Euclidean Voronoi diagram.

Claims9

Dependent claims

A computer implemented method for predicting surface interactions between solids comprising:

using a computer system coupled a database having a first set of spheres, the first set of spheres representing a protein, and a second set of spheres, the second set of spheres representing a ligand, having instructions to create a three-dimensional graphical representation of a set of predicted biological interactions between docking surfaces of the protein and the ligand by:
accessing the database having a first and second set of spheres;
mathematically computing a Euclidean Voronoi diagram for the protein based upon the first set of spheres;
computing a first molecular surface using the mathematically-computed Euclidean Voronoi diagram for the protein;
mathematically computing a Euclidean Voronoi diagram for the ligand based upon the second set of spheres;
computing a second molecular surface using the mathematically-computed Euclidean Voronoi diagram for the ligand;
and
determining the set of predicted biological interactions between docking surfaces based on whether a part of the second molecular surface docks into a part of the first molecular surface;
and
causing the three-dimensional graphical representation of the set of predicted biological interactions between docking surfaces of the protein and the ligand to be presented on a display apparatus,
wherein mathematically computing the Euclidean Voronoi diagram for the ligand comprises:
finding an initial vertex, the initial vertex being associated with a sphere from the second set of spheres;
generating an edge that emanates from the initial vertex, the edge being mathematically defined;
and
computing an empty sphere from the generated edge to define an end vertex of the generated edge.

12 more elements

Dependencies are inferred from the claim text.

Facts

Application: 11/120,743Filed 3 May 2005 · us provisional application
Priority: 4 May 2004
Published: US 2005/0248567 A110 Nov 2005
Granted: 16 Mar 2010
Term ends: Not estimatedThe source records don’t support an estimate.

Classification6 codes

G06T 17/20
Three-dimensional [3D] modelling for computer graphics: finite element generation, e.g. wire-frame surface description, tesselation
G16B 15/30
ICT specially adapted for analysing two-dimensional [2D] or three-dimensional [3D] molecular structures, e.g. structural or functional relations…:…
G16B 45/00
Ict specially adapted for bioinformatics-related data visualisation
G16B 15/00
Ict specially adapted for analysing two-dimensional [2d] or three-dimensional [3d] molecular structures