Calculating three-dimensional (3D) Voronoi diagrams

Details Calculating three-dimensional (3D) Voronoi diagrams Calculating three-dimensional (3D) Voronoi diagrams

2010-02-03

2010-11-02

Pappas, Peter-Anthony (Department: 2628)

Computer graphics processing and selective visual display system

Computer graphics processing

Three-dimension

Reexamination Certificate

active

07825927

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.

REFERENCES:
patent: 6182016 (2001-01-01), Liang et al.
patent: 6384826 (2002-05-01), Bern et al.
patent: 6631202 (2003-10-01), Hale
patent: 7050612 (2006-05-01), Hale
patent: 2003/0149537 (2003-08-01), Binkowski et al.
patent: 2004/0249809 (2004-12-01), Ramani et al.
patent: 2005/0089878 (2005-04-01), Debe et al.
patent: 2005/0192758 (2005-09-01), Xie
Boris Delaunay. Sur la Sphere Vide. Proceedings of the International Mathematical Congress in Toronto. 1924.
Golias et al. Delaunay Triangulation and 3D Adaptive Mesh Generation. Finite Elements in Analysis and Design. 1997.
Gavrilova et al. Updating the Topology of the Dynamic Voronoi Diagram for Spheres in Euclidean d-dimensional Space. Comptuer Aided Geometric Design. 2003.
Application and File History of U.S. Appl. No. 11/120,743, Inventors Deok-Soo Kim et al., filed May 3, 2005, now U.S. Patent No. 7,679,615, issued Mar. 16, 2010, as available on PAIR at www.uspto.gov.
Application and File History of U.S. Appl. No. 11/378,742, Inventors Deok-Soo Kim et al., filed Mar. 17, 2006, as available on PAIR at www.uspto.gov.
Chong-Min Kim, Youngsong Cho, Byunghoon Lee, Jeongyoun Seo, Sang-Min Park, Chung-In Won, Donguk Kim and Deok-Soo Kim, “Interface surfaces for protein-protein interaction: Voronoi diagram based approach,” 2005 CAD/CAM.
Donguk Kim, Youngsong Cho, Deok-Soo Kim, “Algorithms for constructing Euclidean Voronoi diagrams for spheres in 3D: an edge tracing algorithm and a region expansion algorithm,” 2005 CAD/CAM.
Deok-Soo Kim, Cheol-Hyung Cho, Youngsong Cho, Donguk Kim, “Pocket recognition on a protein using Euclidean Voronoi diagram of atoms,” pp. 1-23.
Deok-Soo Kim, Youngsong Cho, Donguk Kim, Sangsoo Kim, Jonghwa Bhak, Sung-Hoon Lee, “Euclidean Voronoi iagrams oOD spheres and applications to protein structure analysis,” Running Title: Euclidean Voronoi Diagrams of Spheres, pp. 1-22.
V.A. Luchnikov, N.N. Medvedev, L. Oger and J.-P. Troadec, “Voronoi-Delaunay analysis of voids in systems of nonspherical particles,” Physical Review E, vol. 59, No. 6, Jun. 1999, pp. 7205-7212.
Deok-Soo Kim, Youngsong Cho and Donguk Kim, “Euclidean Voronoi diagram of 3D balls and its computation via tracing edges,” Jan. 31, 2005, pp. 1-28.
Donguk Kim, Deok-Soo Kim, “Euclidean Voronoi diagrams for spheres in 3D by expanding regions,” pp. 1-10.
Donguk Kim, Youngsong Cho, and Deok-Soo Kim, “Region expansion by flipping edges for Euclidean Voronoi diagrams of 3D spheres based on a radial data structure”.
Deok-Soo Kim, Youngsong Cho, Donguk Kim, “Edge-tracing algorithm for Euclidean Voronoi diagram of 3D spheres,” 16thCanadian Conference on Computational Geometry, 2004, Montreal, Quebec, Aug. 9-11, 2004, pp. 176-179.
Subject: patent related papers and issues.
Deok-Soo Kim, Youngsong Cho, Donguk Kim, “Euclidean Voronoi diagram of3D spheres by tracing edges,” Hanyang University.
Cheol-Hyung Cho, Youngsong Cho, Donguk Kim, Deok-Soo Kim, “Pockets Recognition on Proteins: Euclidean Voronoi Diagram and Convex Hull Based Approach,” 2005CAD/CAM.
Deok-Soo Kim, Youngsong Cho, Donguk Kim, “Edge-tracing algorithm for Euclidean Voronoi diagram of3D spheres,” 16thCanadian Conference on Computational Geometry, 2004, Montreal, Quebec, Aug. 9-11, 2004, pp. 176-179.
Deok-Soo Kim, Donguk Kim, Youngsong Cho, Joonghyun Ryu, Cheol-Hyung Cho, Joon Young Park, and Hyun Chan Lee, “Visualization and analysis of protein structures using Euclidean Voronoi diagram of atoms”.
A. Goede, R. Preissner, C. Frommel, “Voronoi Cell: New Method for Allocation of Space among Atoms: Elimination of Avoidable Errors in Calculation of Atomic Volume and Density,” CCC 0192-8651/97/0911 I3-II, vol. 18, No. 9, Journal of Computational Chemistry, pp. 1113-1123.
Deok-Soo Kim, Donguk Kim, Kokichi Sugihara, “Voronoi diagram of a circle set from Voronoi diagram ofa point set: 1. Topology,” Computer Aided Geometric Design 18 (2001) 541-562, www.elsevier.com/locate/comaid.
Deok-Soo Kim, Donguk Kim, Kokichi Sugihara, “Voronoi diagram of a circle set from Voronoi diagram ofa point set: 1. Geometry,” Computer Aided Geometric Design 18 (2001) 563-585, www.elsevier.comllocate/comaid.
Hans-Martin Will, “Computation of Additively Weighted Voronoi Cells for Applications in Molecular Biology,” Diss. ETH No. 13188, 1999, pp. 1-161.
Joonghyun Ryu, Rhohun Park, Byunghoon Lee, Youngsong Cho, Donguk Kim, Deok-Soo Kim, “Computing molecular surfaces of a protein: an approach based on a Voronoi diagram and a ball blending,” Molecular Surface, 2005CAD/CAM.
Jonghyun Ryu, Donguk Kim, Youngsong Cho, Rhohun Park and Deok-Soo Kim, “Computation of Molecular Surface Using Euclidean Voronoi Diagram,” Computer-Aided Design & Applications, vol. 2, Nos. 1-4, 2005, pp. xxx-yyy, pp. 1-10.
Deok-Soo Kim, Cheol-Hyung Cho, Youngsong Cho, Chung In Won, and Dounguk Kim, “Pocket recognition on a protein using Euclidean Voronoi diagram of atoms”.
Deok-Soo Kim, Yong-Chae Chung, Sangwon Seo, Sang-Pil Kim and Chong Min Kim, “Distributions of BCC, FCC, and HCP structures in AI-Co composite materials,” Journal of Ceramic Processing Research, vol. 6, No. I, pp. 0-00 (2004), pp. 1-5.
Deok-Soo Kim, Yong-Chae Chung, Sangwon Seo, Sang-Pil Kim and Chong Min Kim, “Crystal structure extraction in materials using Euclidean Voronoi diagram and angular distributions among atoms,” Journal of Ceramic Processing Research, vol. 6, No. I, pp. 0-00 (2004), pp. 1-5.
Deok-Soo Kim, Youngsong Cho, Donguk Kim, Sangsoo Kim, Jonghwa Bhak, Sung-Hoon Lee, “Euclidean Voronoi diagram of 3D spheres and applications to protein structure analysis”.
Deok-Soo Kim, Youngsong Cho, Donguk Kim, Cheol-Hyung Cho, “Protein structure analysis using Euclidean Voronoi Diagram of atoms,” pp. 1-5.
Amitabh Varshney, Frederick P. Brooks, Jr., David C. Richardson, William V. Wright, Dinesh Manocha, “Defining, Computing, and Visualizing Molecular Interfaces,” Proceedings, IEEE Visualization 95, Oct. 29-Nov. 3, 1995, Atlanta, GA, pp. 36-43.
Borislav Angelov, Jean-Francois Sadoc, Rerni Jullien, Alain Soyer, Jean-Paul Momon, “Nonatomic Solvent-Driven Voronoi Tessellation of Proteins: An Open Tool to Analyze Protein Folds,” Proteins: Structure, Function, and Genetics 49:446-456 (2002).
Alain Soyer, Jacques Chomilier, Jean-Paul Momon, Rerni Jullien, and Jean-Francois Sadoc, “Voronoi' Tessellation Reveals the Condensed Matter Character of Folded Proteins,” vol. 85, No. 16, Physical Review Letters, Oct. 16, 2000, pp. 3532-3535.
Anne Poupon, “Voronoi and Voronoi-related tessellations in studies of protein structure and interaction,” www.sciencedirecto.com, Current Opinion in Structural Biology 2004, 14:233-241.
Klaus P. Peters, Jana Fauck and Cornelius Frommel, “The Automatic Search for Ligand Binding Sites in Proteins of Known Three-dimensional Structure Using only Geometric Criteria,” J. Mol. Biol. (1996) 256, 201

Affiliated with

Also associated with

Rating

Calculating three-dimensional (3D) Voronoi diagrams does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Calculating three-dimensional (3D) Voronoi diagrams, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Calculating three-dimensional (3D) Voronoi diagrams will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4169172