Reduction of the Search Space in the Edge-Tracing Algorithm for the Voronoi Diagram of 3D Balls

1. Okabe, A., Boots, B., Sugihara, K., Chiu, S.N.: Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, 2nd edn. John Wiley & Sons, Chichester (1999)

   Google Scholar 

2. Goede, A., Preissner, R., Frömmel, C.: Voronoi cell: New method for allocation of space among atoms: Elimination of avoidable errors in calculation of atomic volume and density. Journal of Computational Chemistry 18(9), 1113–1123 (1997)

   Article  Google Scholar 

3. Kim, D.S., Cho, Y., Kim, D., Cho, C.H.: Protein sructure analysis using Euclidean Voronoi diagram of atoms. In: Proceedings of the International Workshop on Biometric Technologies (BT 2004), pp. 125–129 (2004)

   Google Scholar 

4. Kim, D.S., Cho, C.H., Kim, D., Cho, Y.: Recognition of docking sites on a protein using β-shape based on voronoi diagram of atoms. Computer-Aided Design (2005) (in printing)

   Google Scholar 

5. Richards, F.M.: The interpretation of protein structures: Total volume, group volume distributions and packing density. Journal of Molecular Biology 82, 1–14 (1974)

   Article  Google Scholar 

6. Aurenhammer, F.: Power diagrams: Properties, algorithms and applications. SIAM Journal on Computing 16, 78–96 (1987)

   Article  MATH  MathSciNet  Google Scholar 

7. Boissonnat, J.D., Karavelas, M.I.: On the combinatorial complexity of Euclidean Voronoi cells and convex hulls of d-dimensional spheres. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 305–312 (2003)

   Google Scholar 

8. Gavrilova, M.: Proximity and Applications in General Metrics. PhD thesis, Department of Computer Science, The University of Calgary, Calgary, Canada (1998)

   Google Scholar 

9. Gavrilova, M., Rokne, J.: Updating the topology of the dynamic Voronoi diagram for spheres in Euclidean d-dimensional space. Computer Aided Geometric Design 20(4), 231–242 (2003)

   MATH  MathSciNet  Google Scholar 

10. Kim, D.S., Cho, Y., Kim, D.: Euclidean Voronoi diagram of 3D balls and its computation via tracing edges. Computer-Aided Design 37(13), 1412–1424 (2005)

    Article  MATH  Google Scholar 

11. Luchnikov, V.A., Medvedev, N.N., Oger, L., Troadec, J.P.: Voronoi-Delaunay analysis of voids in systems of nonpherical particles. Physical Review E 59(6), 7205–7212 (1999)

    Article  Google Scholar 

12. Will, H.M.: Computation of Additively Weighted Voronoi Cells for Applications in Molecular Biology. PhD thesis, Swiss Federal Institute of Technology, Zurich (1999)

    Google Scholar 

13. Cho, Y., Kim, D., Kim, D.S.: Topology representation for the Voronoi diagram of 3D spheres. International Journal of CAD/CAM 5(3) (2005) (in printing)

    Google Scholar 

14. RCSB Protein Data Bank Homepage (2005), http://www.rcsb.org/pdb/

15. Halperin, D., Overmars, M.H.: Spheres, molecules, and hidden surface removal. In: Proceedings of the 10th ACM Symposium on Computational Geometry, pp. 113–122 (1994)

    Google Scholar 

Download references