Kokichi Sugihara, University of Tokyo

Dr. Kokichi Sugihara received a Bachelors of Engineering, a Masters of Engineering and a Doctor of Engineering in 1971, 1973, and 1980, respectively from the University of Tokyo. He worked at Electro Technical Laboratories and Nagoya University and presently is a professor at the University of Tokyo. His research interest includes mathematical engineering, computational geometry, robust computation, computer vision and computer graphics. He is the author of "Machine Interpretation of Line Drawings" (MIT Press, 1986), and one of the coauthors of "Spatial Tessellations --- Concepts and Applications of Voronoi Diagrams" (John Wiley and Sons, First Edition in 1991, and Second Edition in 2000).

Title: Toward Superrobust Geometric Computation

Abstract:
The robustness against numerical errors is one of the most serious issues in geometric computation, because naively implemented algorithms often fail due to inconsistency caused by numerical errors. To overcome this difficulty many approaches have been proposed; among them the exact computation approach and the topology-oriented approach seem most promising. Actually the exact computation approach employs high-precision arithmetic that is precise enough to judge the topological structures always correctly, and thus constructs a closed error-free world. This approach is usually accompanied by symbolic perturbation to avoid degeneracy and by the floating-point filter to avoid unnecessarily expensive computation. The topology-oriented approach, on the other hand, takes an opposite direction, that is, higher priority is placed on the topological consistency than on numerical values, and thus inconsistency is avoided. These approaches have been successfully applied to the construction of completely robust software for many geometric problems, and hence sometimes they say, for example, "Implementation issue can be solved by exact computation technique, and hence here we concentrate on the theoretical aspect of the algorithm." However, these approaches are still far from complete, because they contain many problems. For example, the exact computation approach sometimes requires very high precision, the symbolic perturbation sometimes produces unwanted side effects, and the topology-oriented approach requires deep insight into individual geometric problems. This talk concentrates on these difficulties, and consider possible directions to overcome them and thus to establish general principles for "superrobust" geometric computation.