›› 2013,Vol. 28 ›› Issue (2): 255-266.doi: 10.1007/s11390-013-1327-3

所属专题: Computer Graphics and Multimedia

• Special Section on Selected Paper from NPC 2011 • 上一篇    下一篇


François Anton1, Darka Mioc1, and Marcelo Santos2   

  • 收稿日期:2012-02-08 修回日期:2013-01-14 出版日期:2013-03-05 发布日期:2013-03-05

Exact Computation of the Topology and Geometric Invariants of the Voronoi Diagram of Spheres in 3D

François Anton1, Darka Mioc1, and Marcelo Santos2   

  1. 1 Research Division of Geodesy, National Space Institute, Technical University of Denmark, Kongens Lyngby, Denmark;
    2 Department of Geodesy and Geomatics Engineering, University of New Brunswick, Fredericton, New Brunswick, Canada
  • Received:2012-02-08 Revised:2013-01-14 Online:2013-03-05 Published:2013-03-05

本文讨论了基于吴氏算法进行球体Voronoi图和Delaunay三角化的精确计算问题。本文的主要贡献首先在于给出了一个自动推导用于Delaunay空包围球和四个球确定一个Voronoi顶点的判定准则的不变量;其次我们应用这种自动推导方法来得到精确计算球体Voronoi 图和Delaunay对偶图的所有几何不变量。就我们所知, 目前还没有关于使用几何不变量来精确计算球体Voronoi 图和Delaunay对偶图的详细论述。我们从定义描述问题的0维代数集的系统方程出发, 应用吴氏算法将初始系统方程转化为一个等价的吴氏示性集合。在对应的代数系统方程中, 除了第一项的其余所有多项式里从, 从其一多项式继承来的高阶变量都被消除, 并且所得到的最后一个多项式只具有一个变量。通过将多项式中每一单项式的系数重新组合, 我们得到给定问题的不变量多项式。我们将不变量多项式用新的系数替代来重新表达原始系统方程。我们重复这个过程直到找到应用吴氏算法得到的所有不变量的代数关系。最后, 我们提出一个构造球体Voronoi图和Delaunay对偶图的增量式算法并将之应用在测地学中。

Abstract: In this paper, we are addressing the exact computation of the Delaunay graph (or quasi-triangulation) and the Voronoi diagram of spheres using Wu's algorithm. Our main contributions are first a methodology for automated derivation of invariants of the Delaunay empty circumsphere predicate for spheres and the Voronoi vertex of four spheres, then the application of this methodology to get all geometrical invariants that intervene in this problem and the exact computation of the Delaunay graph and the Voronoi diagram of spheres. To the best of our knowledge, there does not exist a comprehensive treatment of the exact computation with geometrical invariants of the Delaunay graph and the Voronoi diagram of spheres. Starting from the system of equations defining the zero-dimensional algebraic set of the problem, we are applying Wu's algorithm to transform the initial system into an equivalent Wu characteristic (triangular) set. In the corresponding system of algebraic equations, in each polynomial (except the first one), the variable with higher order from the preceding polynomial has been eliminated (by pseudo-remainder computations) and the last polynomial we obtain is a polynomial of a single variable. By regrouping all the formal coefficients for each monomial in each polynomial, we get polynomials that are invariants for the given problem. We rewrite the original system by replacing the invariant polynomials by new formal coefficients. We repeat the process until all the algebraic relationships (syzygies) between the invariants have been found by applying Wu's algorithm on the invariants. Finally, we present an incremental algorithm for the construction of Voronoi diagrams and Delaunay graphs of spheres in 3D and its application to Geodesy.

[1] Green P, Sibson R. Computing dirichlet tessellations in theplane. The Computer Journal, 1978, 21(2): 168-173.

[2] Brown K Q. Voronoi diagrams from convex hulls. Informa-tion Processing Letters, 1979, 9(5): 223-228.

[3] Aurenhammer F. Gewichtete Voronoi diagramme: Ge-ometrische deutung und Konstruktions-Algorithmen [Ph.D.Thesis]. IIG-TU Graz, Austria, 1984.

[4] Aurenhammer F, Klein R. Voronoi diagrams. In Handbookof Computational Geometry, Chapter V, Sack J, Urrutia G(eds.), Elsevier Science Publishing, 2000, pp.201-290.

[5] Guibas L J, Knuth D E, Sharir M. Randomized incrementalconstruction of Delaunay and Voronoi diagrams. In Proc. the17th International Colloquium on Automata, Languages andProgramming, July 1990, pp.414-431.

[6] Okabe A, Boots B, Sugihara K. Spatial Tessellations: Con-cepts and Applications of Voronoi Diagrams. John Wiley andSons, 1992.

[7] Kim D S, Cho Y, Kim D. Euclidean Voronoi diagram of 3Dballs and its computation via tracing edges. Computer-AidedDesign, 2005, 37(13): 1412-1424.

[8] Kim D, Kim D S. Region-expansion for the Voronoi diagramof 3D spheres. Comput. Aided Des., 2006, 38(5): 417-430.

[9] Ryu J, Kim D, Cho Y, Park R, Kim D S. Computa-tion of molecular surface using Euclidean Voronoi diagram.Computer-Aided Design and Applications, 2005, 2(1/4).

[10] Kim D S, Cho Y, Kim D, Kim S, Bhak J, Lee S H. EuclideanVoronoi diagrams of 3D spheres and applications to proteinstructure analysis. Japan Journal of Industrial and AppliedMathematics, 2005, 22(2): 251-265.

[11] Will H M. Fast and efficient computation of additivelyweighted Voronoi cells for applications in molecular biology.In Proc. the 6th Scandinavian Workshop on Algorithm The-ory, July 1998, pp.310-321.

[12] Gavrilova M. Proximity and applications in general metrics[Ph.D. Thesis]. University of Calgary, Alberta, Canada, 1998.

[13] Gavrilova M, Rokne J. Updating the topology of the dynamicVoronoi diagram for spheres in Euclidean d-dimensionalspace. Comput. Aided Geom. Des., 2003, 20(4): 231-242.

[14] Gavrilova M. An explicit solution for computing the verticesof the Euclidean d-dimensional Voronoi diagram of spheres ina 皁ating-point arithmetic. International Journal of Compu-tational Geometry and Applications, 2009, 19(5): 415-424.

[15] Wu W T, Gao X S. Automated reasoning and equation solv-ing with the characteristic set method. J. Comput. Sci. &Technol., 2006, 21(5): 756-764.

[16] Nishida T, Sugihara K. Precision necessary for d-dimensionalsphere Voronoi diagrams. In Proc. the 5th InternationalSymposium on Voronoi Diagrams in Science and Engineer-ing, September 2008, pp.157-167.

[17] Nishida T, Tanaka Y, Sugihara K. Evaluation of the precisionfor exact computation of a circle Voronoi diagram. TechnicalReport UW-CS-TR-1481, Department of Mathematical Infor-matics, Graduate School of Information Science and Technol-ogy, The University of Tokyo, Japan, October 2007.

[18] Kim D S, Cho Y, Kim D. Calculating three-dimensional (3D)Voronoi diagrams. Patent No. US7825927, 2010.

[19] Hanniel I, Elber G. Computing the Voronoi cells of planes,spheres and cylinders in R3. Comput. Aided Geom. Des.,2009, 26(6): 695-710.

[20] Anton F. Voronoi diagrams of semi-algebraic sets [Ph.D. The-sis]. The University of British Columbia, Vancouver, Canada,2004.

[21] Anton F. A certified Delaunay graph con癷ct locator for semi-algebraic sets. In Proc. Int. Conf. Computational Scienceand Its Applications, Part I, May 2005, pp.669-682.

[22] Kim D S, Kim D, Cho Y, Sugihara K. Quasi-triangulationand interworld data structure in three dimensions. Computer-aided Design, 2006, 38(7): 808-819.

[23] Kim D S, Cho Y, Sugihara K. Quasi-worlds and quasi-operators on quasi-triangulations. Comput. Aided Des.,2010, 42(10): 874-888.

[24] Anton F, Mioc D, Gold C. The Voronoi diagram of circles andits application to the visualization of the growth of particles.In Transactions on Computational Science III, Gavrilova M,Tan C J (eds.), Berlin, Heidelberg: Springer, 2009, pp.20-54.

[25] Kolmogorov A. A statistical theory for the recrystallizationof metals. Akad. nauk SSSR, Izv., Ser. Matem., 1937, (3):355-359.

[26] Deschamps A. Handbook of Aluminum, New York, USA:Marcel Dekker, Inc., 2005, pp.155-192.

[27] Chen Z, Xu J. Robust algorithm for k-gon Voronoi diagramconstruction. In Proc. the 14th Canadian Conference onComputational Geometry, August 2002, pp.77-81.

[28] Blum L, Cucker F, Shub M, Smale S. Complexity and RealComputation. New York: Springer-Verlag, 1997.

[29] Canny J F, Emiris I Z. A subdivision-based algorithm for thesparse resultant. J. ACM, 2000, 47(3): 417-451.

[30] Voronoï G F. Nouvelles applications des paramètres conti-nus à la théorie des formes quadratiques. Premier mémoire.sur quelques propriétés des formes quadratiques positives par-faites. Journal für die reine und angewandte Mathematik,1908, 1908(133): 97-178. (In French)

[31] Voronoï G F. Nouvelles applications des paramètres conti-nus à la théorie des formes quadratiques. deuxième mémoire.recherches sur les paralléloèdres primitifs. première partie.partition uniforme de l'espace analytique à n dimensions àl'aide des translations d'un m^eme polyèdre convexe. Journalfür die reine und angewandte Mathematik, 1908, 1908(134):198-287. (In French)

[32] Voronoï G F. Nouvelles applications des paramètres conti-nus à la théorie des formes quadratiques. deuxième mémoire.recherches sur les paralléloèdres primitifs. seconde partie. do-maines de formes quadratiques correspondant aux différentstypes de paralléloèdres primitifs. Journal für die reineund angewandte Mathematik, 1909, 1909(136): 67-182. (InFrench)

[33] Greuel G M, Pfister G. A Singular Introduction to Commu-tative Algebra. Berlin: Springer-Verlag, 2002.

[34] Hamelryck T. An amino acid has two sides: A new 2D mea-sure provides a different view of solvent exposure. Proteins:Structure, Function, and Bioinformatics, 2005, 59(1): 38-48.
No related articles found!
Full text



[1] 刘明业; 洪恩宇;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] 陈世华;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] 高庆狮; 张祥; 杨树范; 陈树清;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] 陈肇雄; 高庆狮;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] 黄河燕;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] 闵应骅; 韩智德;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] 唐同诰; 招兆铿;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] 闵应骅;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] 张钹; 张铃;. Statistical Heuristic Search[J]. , 1987, 2(1): 1 -11 .
[10] 朱鸿;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn