维普中文期刊产品整合服务

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

查看全文 作　　者：Franois [1]Anton;Darka [1]Mioc;Marcelo [2]Santos 高影响力作者 机构地区：[1]Research Division of Geodesy, National Space Institute, Technical University of Denmark;[2]Department of Geodesy and Geomatics Engineering, University of New Brunswick高影响力机构 出　　处：《Journal of Computer Science & Technology》索引2013年第28卷第2期,共12页高影响力期刊 摘　　要：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. 关 键 词：几何不变量 计算 VORONOI图 DELAUNAY 多项式不变量 代数方程组 增量算法 3D
相关文献

参考文献(34)

耦合文献(1)

网站首页 | 关于我们 | 联系我们 | 产品服务 | 客服中心 | 广告服务 | 版权声明 | 网站联盟 | 友情链接 | 售卡网点

版权所有© 渝B2-20050021-1　渝公网安备 50019002500403号　违法和不良信息举报中心

互联网出版许可证 新出网证(渝)字10号 全国400电话 - 免长途话费