检索结果-内蒙古大学图书馆

A ROBUST TOPOLOGY-ORIENTED INCREMENTAL ALGORITHM FOR VORONOI DIAGRAMS

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 1994年第2期4卷 179-228页

作者： Sugihara, Kokichi Iri, Masao Univ Tokyo Fac Engn Dept Math Engn & Informat Phys Bunkyo Ku Tokyo 113 Japan

The paper presents a robust algorithm for constructing Voronoi diagrams in the plane. The algorithm is based on an incremental method, but is quite new in that it is robust against numerical errors. Conventionally, geometric algorithms have been designed on the assumption that numerical errors do not take place, and hence they are not necessarily valid for real computers where numerical errors are inevitable. The algorithm to be proposed in this paper, on the other hand, is designed with the recognition that numerical errors are inevitable in real computation;i.e., in the proposed algorithm higher priority is placed on topological structures than on numerical values. As a result, the algorithm is "completely" robust in the sense that it always gives some output however poor the precision of numerical computation may be. In general, the output cannot be more than an approximation to the true Voronoi diagram which we should have got by infinite-precision computation. However, the algorithm is asymptotically correct in the sense that the output converges to the true diagram as the precision becomes higher. Moreover, careful choice of the way of numerical computation makes the algorithm stable enough;indeed the present version of the algorithm can construct in single-precision arithmetic a correct Voronoi diagram for one million generators randomly placed in the unit square in the plane.

关键词： Voronoi diagram robust algorithm topology-oriented method incremental construction combinatorial abstraction asymptotic correctness

来源：评论

学校读者我要写书评

暂无评论

A Robust and Consistent Algorithm for Intersecting Convex Polyhedra

引用

Computer Graphics Forum 1994年第3期13卷 45-54页

作者： Sugihara, Kokichi Department of Mathematical Engineering Faculty of Engineering University of Tokyo Tokyo 113 7‐3‐1 Hongo Bunkyo‐ku Japan

This paper presents a numerically robust and topologically consistent algorithm for intersecting convex polyhedra. This algorithm is new in the sense that the consistency issue is completely separated from the numerical error issue. The intersection operation is combinatorially abstracted as the operation of changing the vertex‐edge graphs associated with the input polyhedra, and numerical computation is employed only for choosing the branch of processing which is most likely to lead to the correct solution of the problem. Hence, the resultant algorithm is completely free from topological inconsistency. © 1994 Eurographics Association

关键词： combinatorial abstraction convex polyhedron robust algorithm solid modeling

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：