# 超ロバスト計算原理セミナー（２月６日、２件）

投稿日： 投稿者： 2004/01/30 杉原厚吉
```超ロバスト計算原理「ロバスト幾何計算」セミナー

(今回は2名の連続講演をお願いしました．)

テーマ：Theory of Guaranteed Accuracy Computation

is a ubiquitous and well-known problem in all areas
of scientific and engineering computation.
Programs“crash”and there is no systematic solution
for it until recently. Much progress has been
achieved in the last 10 years: we can now routinely
achieve fully robust algorithms for a large class
of problems.  The key idea here is the idea of
“guaranteed sign computation”.

“Guaranteed accuracy computation”is a natural
generalize of guaranteed sign computation:
the user can specify any relative or absolute
error bound on the computed values. Two current
software libraries, Core Library and LEDA Real,
support this mode.

In this talk, we survey some current research.
Then we present a theory of real approximation
to capture guaranteed accuracy computation.
This is formulated in terms of Turing computability,
as well as via a novel“numerical model of computation”.
Relationship to the model of Blum, Shub, Smale
(BSS, 1989) will be noted.

Core Library Project, http://cs.nyu.edu/exact/core/

http://cs.nyu.edu/exact/doc/guaranteed.ps.gz

テーマ：Voronoi diagram for spheres and its applications

for circles in a plane and for spheres in 3D will be discussed.
Taking advantage of the similarity in the topologies of point set
Voronoi diagram of center points of circles and the Voronoi
diagram of circles, we have devised a simple edge-flipping
algorithm to transform point set Voronoi diagram to circle set
Voronoi diagram. It turns out that the transformation takes only
O(N^2) in the worst-case.  On the other hand, Voronoi diagram
of spheres in 3D can be computed in a different manner.
Starting from a Voronoi vertex among  four spheres,
we trace Voronoi edges until all edges are
explored. In our representation, the Voronoi edges and Voronoi
faces are represented in rational  quadratic Bezier form.
Based on these Voronoi diagrams, we will discuss a few important
applications that Voronoi diagrams play major roles.
In addition, future research directions will be also presented.

```