Events & News
Colloquium
| Category | Lecture |
| Date | Thursday, March 4, 2010 |
| Time | 11:00 am |
| Location | GS 906 |
| Details | Light refreshments - 9th floor Atrium - 10:45 am |
| Speaker | Tetsuo Asano |
| Title | School of Information Science |
| Affiliation | JAIST (Japan Advanced Institute of Science and Technology) |
Constant-Work-Space Algorithm for Geometric Problems
Abstract: I will talk about space-efficient algorithms for geometric problems in a restricted computational model called ``constant work space''
or ``log-space'' computation. I start with an algorithm for drawing
a Delaunay triangulation of a planar point set and then extend it
to another algorithm for drawing a Voronoi diagram.
There are $\Theta(n \log n)$-time algorithms for those problems in a
standard computational model for $n$ points. Our algorithms run in
$O(n2)$ time using only a constant number of storage cells of
$O(\log n)$ bits in total. Then, I will give a cubic-time algorithm
for computing a Euclidean minimum spanning tree for a point set.
The fourth problem is to find a simple path between two arbitrary
nodes in a tree of $n$ nodes. Our algorithm runs in $O(n^{1+\epsilon})$
time using work space of size $O(1/\epsilon)$ for any small constant
$\epsilon > 0$. Then, I will describe how to compute a shortest
path between two points in a simple $n$-gon. Although the shortest
path problem in general graphs is NL-complete, this constrained
problem can be solved in quadratic time using only constant work
space.
Biography
Dr. Tetsuo Asano was born in Kyoto Prefecture, Japan, in 1949.
He got B.E., M.E., and Ph.D degrees from Osaka University, Japan,
in 1972, 1974, and 1977, respectively. In 1977 he joined
Osaka Electro-Communication University as a lecturer and moved to
JAIST (Japan Advanced Institute of Science and technology) in 1997.
He is now a professor in School of Information Science. He served
as a Presidential Advisor in 1999-2000 and as a senetor in
2001-2003. His research interest includes algorithms and data
structures, especially in computational geometry, combinatorial
optimization, computer graphics, computer vision using geometric
information, and VLSI layout design. He has been serving as editors
of several journals including Discrete and Computational Geometry,
Computational Geometry: Theory and Applications, International
Journal of Computational Geometry and Applications, and Theory of
Computing Sysytems. He has contributed to ACM Annual Symposium on
Computational Geometry as a program committee member in 1990, 1994,
1996, and 2004. He served as a chair of a Special Interest
Group on Algorithms of Information Processing Society of Japan in
1994-1996. He is fellows of Association of Computing Machinery
2001) and Information Processing Soceity of Japan (2004).
Currently he is an advisor to the President of JAIST on education
and will be a director of a new center for education at JAIST.