权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Practical Computational Geometry - Unifying Study on Robust Geometric Computation

实用计算几何-鲁棒几何计算的统一研究

基本信息

批准号：
10358005
负责人：
SUGIHARA Kokichi
金额：
$ 22.09万
依托单位：
The University of Tokyo
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (A)
财政年份：
1998
资助国家：
日本
起止时间：
1998 至 2001
项目状态：
已结题

项目摘要

The goal of this approach is to compare various robust algorithms for geometric computation and to offer general advantages and disadvantages of the algorithms to users who want to choose algorithms that are suitable to their own purpose. The algorithm we studied can be divided into three approaches. The first is a pixel-boxel approach, which includes Asano's optimization for digital images, Inui's process planning algorithms, Kimura's soft object representation. The second is the topological approach, which includes Ohsawa's space modeling, Higashi's topologically-constrained computation, Sugihara's topology-oriented algorithms. The third is the algebraic approach, which includes Imai's optimization algorithms based on Grobner basis, Hirukawa's silhouette algorithms, and Sugihara's generalized Minkowski operations.These methods were applied to off-set computation, digital halftoning, crystal Voronoi diagram, soft-object modeling, simulation of surgical operation, solid modeling, collision detection, geometric packing, parametric shape design, minimum-cost flow, robot motion planning, mesh smoothing, and Minkowski sums. According to these experiences, we recognized that (i) the first approach is simple and suitable for low-dimensional problems, but is difficult to apply to high-dimensional problems, (ii) the second approach can be used in any numerical precision, but requires individual insight to each geometric problem, and (iii) the third approach can be used to any-dimensional problems, but requires special computational environment.

该方法的目的是比较各种稳健的几何计算算法，并给出算法的一般优缺点，以供用户选择适合自己目的的算法。我们研究的算法可以分为三种方法。第一种是像素盒方法，它包括浅野的数字图像优化、Inui的工艺规划算法、木村的软对象表示。第二种是拓扑法，包括Ohsawa的空间建模、Higashi的拓扑受限计算、Sugihara的面向拓扑的算法。第三种是代数方法，包括基于Grobner基的Imai优化算法、Hirukawa的轮廓算法和Sugihara的广义Minkowski操作，这些方法被应用于偏置计算、数字半色调、晶体Voronoi图、软对象建模、手术仿真、实体建模、碰撞检测、几何布局、参数形状设计、最小代价流、机器人运动规划、网格平滑和Minkowski和。根据这些经验，我们认识到：(I)第一种方法简单，适用于低维问题，但很难应用于高维问题；(Ii)第二种方法可以用于任何数值精度，但需要对每个几何问题有独立的洞察力；(Iii)第三种方法可以用于任何维问题，但需要特殊的计算环境。