超ロバスト計算原理セミナー(2月6日、2件)

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

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

会 場:東京大学工学部 6 号館 3 階セミナー室A

日 時: 2004 年 2 月 6 日 (金) 15 時〜16 時

講演者: Professor Chee Yap (New York University)
テーマ:Theory of Guaranteed Accuracy Computation
概 要: Nonrobustness of geometric 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.

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

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

日 時: 2004 年 2 月 6 日 (金) 16 時〜17 時

講演者:Professor Deok-Soo Kim (Hanyang University)
テーマ:Voronoi diagram for spheres and its applications
概 要:In this talk, the construction of Voronoi diagram 
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. 

連絡先:杉原厚吉 (内線 26905)