Joint Research on Discrete and Computational Geometry

在多媒体时代，利用计算机对几何信息进行高速处理是非常重要的。这项联合研究的目的是为离散和计算几何开发有效的算法。Voronoi图、三角剖分、凸多面体等是数学中的基本概念，应用中出现的许多问题都可以用这些概念来解决。本文从理论上研究了三角剖分和凸多面体的数学和算法，在多媒体时代，地理信息系统（GIS）得到了广泛的研究，在GIS中需要解决许多几何信息的问题，Voronoi图在GIS中得到了直接的应用，本文将Voronoi图推广到统计参数空间的图。当GIS与人口数据等其他数据相结合时，空间就变成了高维几何空间，我们的广义图可以用来寻找邻近关系等，通过计算几何算法。我们还开发了有效的几何聚类算法，无论是在欧氏空间和信息几何空间，并将其应用到地理数据挖掘。研究了地图标注问题和点定位问题。关于地图标注问题，地铁地图进行了深入的研究，对应于每一条地铁线路的标签自动放置在一个美丽的方式。

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.