Numerical Stabilization of Geometric Algorithms and Its Applications
几何算法的数值稳定性及其应用
基本信息
- 批准号:01550279
- 负责人:
- 金额:$ 1.54万
- 依托单位:
- 依托单位国家:日本
- 项目类别:Grant-in-Aid for General Scientific Research (C)
- 财政年份:1989
- 资助国家:日本
- 起止时间:1989 至 1991
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
Conventionally, geometric algorithms have been designed on the assumption that numerical errors do not take place, and consequently they are not necessarily valid in real computation where numerical errors are inevitable. We searched for a method for designing geometric algorithms that are robust against numerical errors, and established a new design methodology in which the highest priority is placed on the topological consistency of geometric objects and numerical results are used as lower-priority information. Algorithms thus designed does not come across inconsistency and hence carries out its task, giving some output that is at least topologically consistent. This design methodology was applied to design robust algorithms for the problems : (1) the incremental construction of two-dimensional Voronoi diagrams for points, (2) the divide-and-conquer construction of two-dimensional Voronoi diagrams for points, (3) the incremental construction of two-dimensional Voronoi diagrams for li … More ne segments, (4) the incremental construction of three-dimensional Voronoi diagrams for points, (5) the extraction of intersections of line segments, (6) the construction of three-dimensional convex hulls of points, (7) the set-theoretic operations of simple polygons, (8) the intersection of convex polyhedra, and (9) the construction of Laguerre Voronoi diagrams in the plane. In particular, the new algorithms for the problems (1)-(5) were implemented into computer programs, and computational experiments were corried out. The experiments show that, no matter how poor the precision in computation may be, the programs do not fail, that the outputs converge to the true solutions as the precision becomes higher, that the new algorithms achieve robustness without increasing time complexity achieved by conventional algorithms, and that the new algorithms are simple because exceptional processing for degenerate cases is not necessary.We also investigated numerical methods required in geometric algorithms. The fast automatic differentiation method were used to obtain the tight bound of numerical errors, and the method was applied to many problems such as geographic optimization based on Voronoi diagrams. A new method for tracing abgebraic curves was also constructed, which can trace both global and micro structures in reasonable time. We could also improve the performance of the programs for the problems (1)-(5) bytuning the ways of numerical computations. Less
传统上,几何算法是在假设不发生数值误差的情况下设计的,因此它们在数值误差不可避免的实际计算中不一定有效。我们寻找一种设计对数值误差具有鲁棒性的几何算法的方法。并建立了一种新的设计方法,其中最高优先级放在几何对象的拓扑一致性上,数值结果用作较低优先级的信息,这样设计的算法不会遇到不一致,因此可以执行其任务,并给出一些输出。至少是该设计方法用于设计以下问题的稳健算法:(1)点的二维 Voronoi 图的增量构造,(2)点的二维 Voronoi 图的分而治之构造, (3)线段二维Voronoi图的增量构建,(4)点三维Voronoi图的增量构建,(5)线段交点的提取,(6)构建三维点的凸包,(7)简单多边形的集合论运算,(8)凸多面体的交集,以及(9)平面上拉盖尔沃罗诺伊图的构造。将问题(1)-(5)实现为计算机程序,并进行了计算实验,实验表明,无论计算精度有多差,程序都不会失败,输出结果是正确的。随着精度的提高,收敛到真实的解,新算法在不增加传统算法的时间复杂度的情况下实现了鲁棒性,并且新算法很简单,因为不需要对退化情况进行特殊处理。我们还研究了利用快速自动微分法获得了数值误差的紧界,并将该方法应用于基于Voronoi图的地理优化等多种问题,并构建了一种新的代数曲线追踪方法。整体结构和微观结构在合理的时间内,我们还可以通过调整数值计算的方式来提高问题(1)-(5)的程序性能。
项目成果
期刊论文数量(72)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
K.Sugihara: "Several approaches to numerical problems in geometric algorithms (in Japanese)" Journal of the Faculty of Engineering of the University of Tokyo. vol.A-27. 40-41 (1989)
K.Sugihara:“几何算法中数值问题的几种方法(日语)”东京大学工学院学报。
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
- 通讯作者:
Kokichi SUGIHARA and Masao IRI: "Construction of the Voronoi diagram for one million generators in single-precision arithmetic" Proceedings of IEEE.
Kokichi SUGIHARA 和 Masao IRI:“单精度算术中一百万个生成器的 Voronoi 图的构造”IEEE 论文集。
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
- 通讯作者:
K.Sugihara: "On finite-precision representations of geometric objects" Journal of Computers and System Sciences. vol.39. 236-247 (1989)
K.Sugihara:“论几何对象的有限精度表示”计算机与系统科学杂志。
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
- 通讯作者:
M.Iri: "Geometrical/geographical optimization and fast automatic differentiation" Yugoslav Journal of Operations Research. 1. 121-134 (1991)
M.Iri:“几何/地理优化和快速自动微分”南斯拉夫运筹学杂志。
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
- 通讯作者:
K.Sugihara: "Voronoi diagrams in a river" International Journal of Computational Geometry and Applications. (to appear). (1992)
K.Sugihara:“河流中的 Voronoi 图”国际计算几何与应用杂志。
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
- 通讯作者:
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
IMAI Toshiyuki其他文献
IMAI Toshiyuki的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('IMAI Toshiyuki', 18)}}的其他基金
Development of the method to lead the location of small housing estate in the urban fringe of outlying cities
边远城市边缘区小型住宅区选址引导办法的制定
- 批准号:
11660249 - 财政年份:1999
- 资助金额:
$ 1.54万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
相似国自然基金
切换拓扑下非线性多自主系统的模糊自适应一致性控制
- 批准号:
- 批准年份:2022
- 资助金额:54 万元
- 项目类别:面上项目
平面-立面-表面集成的多细节层次室内模型空间、拓扑和特征一致性重构
- 批准号:42171422
- 批准年份:2021
- 资助金额:59 万元
- 项目类别:面上项目
非量测影像辅助地面Lidar点云的建筑遗产构件内外拓扑一致性精准建模
- 批准号:42171416
- 批准年份:2021
- 资助金额:54 万元
- 项目类别:面上项目
基于不一致性在线评估的混合拓扑动力电池组自适应建模及状态估计方法
- 批准号:
- 批准年份:2020
- 资助金额:24 万元
- 项目类别:青年科学基金项目
基于差分隐私保护的切换拓扑多智能体系统一致性算法研究
- 批准号:
- 批准年份:2020
- 资助金额:24 万元
- 项目类别:青年科学基金项目
相似海外基金
Processing Tomographic Images for Topological Consistency in Lie Group Shape Models
处理层析图像以实现李群形状模型中的拓扑一致性
- 批准号:
503827-2017 - 财政年份:2019
- 资助金额:
$ 1.54万 - 项目类别:
Postgraduate Scholarships - Doctoral
Processing Tomographic Images for Topological Consistency in Lie Group Shape Models
处理层析图像以实现李群形状模型中的拓扑一致性
- 批准号:
503827-2017 - 财政年份:2018
- 资助金额:
$ 1.54万 - 项目类别:
Postgraduate Scholarships - Doctoral
Processing Tomographic Images for Topological Consistency in Lie Group Shape Models
处理层析图像以实现李群形状模型中的拓扑一致性
- 批准号:
503827-2017 - 财政年份:2017
- 资助金额:
$ 1.54万 - 项目类别:
Postgraduate Scholarships - Doctoral