Joint Research on Discrete and Computational Geometry

点击翻译按钮获取中文摘要

It is very important to process geometric information at high speed by computers in the multimedia era. The aim of this joint research is to develop efficient algorithms for discrete and computational geometry. Voronoi diagrams, triangulations, convex polytopes are basic concepts, and many problems which appear in applications can be solved by those concepts. From the theoretical viewpoint, we study mathematical and algorithmic research for triangulations and convex polytopes.In multimedia era, geographical information systems (GIS for short) have been investigated and we have to solve many problems with geometric information in GIS.The Voronoi diagram has been used directly in GIS, and we generalize it to the diagram in statistical parameter space. When GIS is combined with other data such as population data, the space becomes higher-dimensional geometric space, to which our generalized diagrams can be used to find proximity relations, etc., by using computational-geometric algorithms. We also developed efficient geometric clustering algorithms, both in Euclidean and information geometric spaces, and applied them to geographical data mining. Also, map labeling problem and point location problems are studied. Concerning the map labeling problem, subway maps are intensively studied where labels corresponding to each subway line are automatically placed in a beautiful way.