Research on data structures and optimization problems in GIS

在地理信息系统中，存在着大量的优化问题。为了解决这些问题，迫切需要高效的数据结构和算法来处理海量的地理信息系统数据。我们为地理信息系统中的优化问题开发了数据结构和算法，例如，小学生通勤路线的确定问题，灾难时期的设施选址问题，等等。我们还利用时空网络分析了海上交通。此外，从理论上给出了与交通流中的最小最大流问题密切相关的最小最大匹配问题的两种近似算法。

In the Geographic Information Systems(GIS), there are a lot of optimization problems. In order to solve such problems, efficient data structures and algorithms that deal with a large amount of GIS data are strongly required. We developed data structures and algorithms for optimization problems in GIS, for example, a problem of deciding school-commuting routes for elementary school students, facility location problems in times of disaster, etc. We also analyzed marine transportation using a time-space network. Moreover, from a theoretical point of view, we proposed two approximation algorithms for a minimum maximal matching problem that have a strong relationship with minimum maximal flow problem in traffic flow.