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

計算幾何学の並列ロバスト算法に関する研究

计算几何并行鲁棒算法研究

基本信息

批准号：
08680360
负责人：
陳慰
金额：
$ 1.34万
依托单位：
Nagoya Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
1996
资助国家：
日本
起止时间：
1996 至无数据
项目状态：
已结题

项目摘要

本研究は計算幾何学における効率の良い並列ロバスト算法の開発を目的とする。計算幾何学において最も基本的な問題-凸包問題に着目し、計量誤差と位相誤差の定量的な定義した。そして汎用性のあるPRAM並列計算モデルの上で、並列計算についての計量誤差と逐次計算の誤差との差異や計量性質と位相性質との関係などを解明し、効率の良い並列ロバスト算法を開発した。これらの結果を他の幾何学問題への適応や拡張することなどについても研究が行なわれた。具体的に、位相誤差と計算誤差を表すために、凸包の概念をε-強凸δ-包の概念に拡張する。ここでは、εが位相誤差の尺度、δが計算誤差の尺度である。点集合Sが与えられたとき,ε-強凸δ-包(ε>0)は、各頂点がεの範囲内に移動しても凸性が保つ、そして、凸包との距離がδ以内であるSを含む凸多角形と定義されている。従って、普通の凸包より誤差に強い性質を持つ。Sがn個の点を持つとき、Sのε-強凸O(ε+β)-包(βは単位計算の誤差)をCREW PRAMの上で、O(log^3n)時間、nプロセッサで求める効率のよい並列ロバストアルゴリズムを開発した。定義により、Sの点がε-強凸δ-包の外にあることがあり得る。このため、さらに、包含包の概念を導入し、Sの全ての点を含むε-強凸δ-包含包を定義した。そして、Sのε-強凸O(ε+β)-包含包をO(nlogn)時間で求めるアルゴリズムを提案した。このアルゴリズムは逐次であるが、簡単にPRAMモデルの上で並列化できる。

The purpose of this research is to develop an efficient and well-parallel router algorithm in computational geometry. Convex hull problem, the most fundamental problem in computational geometry, is focused on the quantitative definition of metrology error and phase error. PRAM parallel calculation, parallel calculation, measurement error, error of successive calculation, measurement property, phase property, relationship, solution, efficiency, parallel calculation algorithm The result of this study is that other geometric problems are solved in the same way. The concept of convex hull, ε-strongly convex δ-hull and so on are discussed in detail.ここでは、εが位相误差の尺度、δが计算误差の尺度である。Point set S,ε-strongly convex δ-envelope (ε>0)従って、普通の凸包より误差に强い性质を持つ。S n points, S-strongly convex O(ε+β)-package (βDefinition The concept of inclusion package is introduced, and the concept of inclusion package is defined. S ε-strongly convex O(ε+β)-containing O(nlogn) time This is the first time I've seen a PRAM.