Realization of Geographic Information Systems with High-Quality Processing Based on Computational Geometry

本研究从计算几何的角度对地理信息系统(简称GIS)和智能交通系统(简称ITS)进行了研究，以满足在这两个领域实现高质量、健壮和快速系统的新需求。从计算几何的角度出发，提出了欧氏几何空间和信息几何空间中的高效几何聚类算法，并将其应用于地理数据挖掘。研究了地图标注问题和地图匹配问题，利用稳健算法构造Voronio图和平面上点的Delaunay三角剖分，提出了一种高效、简便的计算城镇地图医疗轴线作为道路中心线的方法。有了这样好的工具，这种看似复杂的问题，实际上可以非常精准地解决。关于地图标注问题，对地铁地图进行了深入的研究，其中每条地铁线对应的标签都自动以漂亮的方式放置。关于ITS，我们提出了一种智能算法，为高级汽车导航寻找有意义的弯路。此外，还提出了一种从两个相距较远的点获取简单传感器数据来测量交通流量的新方法。Voronoi图已直接应用于地理信息系统中，我们将其推广到统计参数空间的Voronoi图。当地理信息系统与人口数据等其他数据结合在一起时，空间就变成了高维几何空间，我们的广义图可以用来通过计算几何算法找到接近关系等。

In this research, geographical information systems (GIS for short) as well as intelligent transport systems (ITS for short) have been investigated from the viewpoint of computational geometry to meet emerging demands to realize high-quality, robust and fast systems in both fields. From the viewpoint of computational geometry, 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 map matching problems are studied.Specifically, by using robust algorithm to construct the Voronio diagram and Delaunay triangulation of points in the plane, we developed an efficient and simple method of computing the medical axis, as central lines of roads, for town maps. With such nice tools, this kind of seemingly complicated problem can be solved in practice in a very precise manner. Concerning the map labeling problem, subway maps are intensively studied where labels corresponding to each subway line are automatically placed in a beautiful way. Concerning ITS, we have proposed an intelligent algorithm to find meaningful detours for high-level car navigation. Also, a new method of measuring traffic flows from simple sensor data derived at two distant points is presented. The Voronoi diagram has bee 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.