Joint Research on Discrete and Computational Geometry

离散与计算几何联合研究

• 批准号: 10044174
• 负责人: IMAI Keiko
• 金额: $ 3.58万
• 依托单位: Chuo University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (B).
• 财政年份: 1998
• 资助国家: 日本
• 起止时间: 1998 至 2000
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-10044174/
• 关键词: discrete geometry; computational geometry; geographical information system; Voronoi diagram; triangulation; convex polytope; geographical database; 地理データベース; クラスタリング; 点位置決定問題; 計算幾何; 離散幾何; 配送計画; 3角形分割; マルチメディア探索; 列挙と数え上げ

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.

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

项目成果

Keiko Imai: "Structures of Triangulations of Points"IEICE Transactions out Information and Systems. E83-D・3. 428-437 (2000)

Keiko Imai：“点三角剖分的结构”IEICE 信息和系统交易 E83-D·3（2000）。

今井桂子: "ラベル配置問題とその路線図への応用"「第5回"統合型地理情報システム"シンポジウム」予稿集. 17-24 (2000)

Keiko Imai：“标签放置问题及其在路线图上的应用”第五届“综合地理信息系统”研讨会论文集 17-24（2000 年）。

M.Inaba and H.Imai: "Geometric Clusteing Models for Multimedia Databases" Proc.10th Canadian Conf.on Computational Geometry. 110-111 (1998)

M.Inaba 和 H.Imai：“多媒体数据库的几何聚类模型”Proc.10th Canadian Conf.on Computational Geometry。

H.Imai, K.Imai, K.Inaba and K.Kubota: "GIS and ITS Infrastructures in Japan-Standardization and Network-Algorithmic Applications"Proceedings of the International Workshop on Emerging Technologies for Geo-Based Applications. 153-167 (2000)

H.Imai、K.Imai、K.Inaba 和 K.Kubota：“日本的 GIS 和 ITS 基础设施 - 标准化和网络算法应用”基于地理应用的新兴技术国际研讨会论文集。

S.Moriyama: "Incremental Construction Properties in Dimension Two - Shellability, Extendable Shellability and Vertex Decomposability"Proceedings of the 12th Annual Canadian Conference on Computational Geometry. 65-72 (2000)

S.Moriyama：“二维增量构造属性 - 可壳性、可扩展可壳性和顶点可分解性”第 12 届加拿大计算几何年会论文集。