Research on Algorithms for Discrete Geometric Structures

离散几何结构算法研究

• 批准号: 10205223
• 负责人: IMAI Keiko
• 金额: $ 6.53万
• 依托单位: Chuo University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research on Priority Areas (B)
• 财政年份: 1998
• 资助国家: 日本
• 起止时间: 1998 至 2000
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10205223/
• 关键词: Computational Geometry; Geometric Structure; Geographic Information System; Label Placement Problems; Point Location; Computational Topology; Topological Invariant; 動的・実時間環境; 計算幾何学; NP困難問題; 地理情報システム; Jones多項式; 三角形分割; Voronoi図; 凸多面体; 列挙問題

The aim of this research is to develop efficient algorithms for discrete problems with geometric information under dynamic and on-line environments. Many practical problems have dynamic and on-line natures, and those discrete structures include geometric information. Many efficient results have been investigated for static discrete problems. However, algorithms should be newly designed to handle dynamic and on-line factors and geometric structures.First, we investigate fundamental concepts in computational geometry such as Voronoi diagrams and triangulations in dynamic environments. We develop algorithms for dynamic Voronoi diagrams and apply them to geometric fitting problems and polygon containment problems. Triangulation is also one of the important concepts in computational geometry, and we research on structures of triangulations of points.In geographic information systems (GIS), there are many geometric problems with dynamic and on-line environments, and we mainly focus on map labeling problems. Map labeling problems are important in GIS, and NP-hard in general. We consider the problem for labeling points and curves on maps drawn from digital data. Our algorithm labels points and curves simultaneously in a beautiful way. Computational results for subway and JR railroad maps in Tokyo are also reported. Moreover, we consider a new model in the node label placement problems. In the model, each label connects with the corresponding point by means of a leader line, and we propose some algorithms for the problem.In dynamic and on-line environments, we have to handle topological changes of geometric structure. In terms of this standpoint, we investigate the Jones polynomial, which is an invariant in knot theory. It is shown that the new algorithm of computing the Tutte polynomial can be applied to computing the Jones polynomial of an arbitrary link. Although computing the Jones polynomial is #P-hard, it can be calculated for some large links.

本研究的目的是发展有效的算法，在动态和在线环境下的几何信息的离散问题。许多实际问题具有动态性和在线性，而这些离散结构又包含几何信息。对于静态离散问题，已有许多有效的结果。然而，算法应重新设计，以处理动态和在线的因素和几何结构。首先，我们调查计算几何中的基本概念，如Voronoi图和三角剖分在动态环境中。我们开发的动态Voronoi图的算法，并将其应用到几何拟合问题和多边形包含问题。三角剖分也是计算几何中的一个重要概念，本文主要研究点的三角剖分结构。在地理信息系统（GIS）中，有许多动态、在线的几何问题，本文主要研究地图标注问题。地图标注问题是地理信息系统中的一个重要问题，一般来说是NP难问题。我们考虑的问题，标记点和曲线的地图上绘制的数字数据。我们的算法以一种美丽的方式同时标记点和曲线。还报告了东京地铁和JR铁路地图的计算结果。此外，我们考虑了一个新的模型中的节点标签放置问题。在模型中，每个标号通过一条引线与对应的点相连，并给出了相应的算法。在动态和在线环境中，需要处理几何结构的拓扑变化。根据这一观点，我们研究琼斯多项式，这是一个不变量的纽结理论。计算结果表明，新的Tutte多项式算法可用于计算任意链环的Jones多项式。虽然计算琼斯多项式是#P-hard，但它可以计算一些大型链接。

项目成果

関根京子,今井浩,今井桂子: "Jones多項式の計算"日本応用数理学会論文誌. 8,3. 341-354 (1998)

Kyoko Sekine、Hiroshi Imai、Keiko Imai：“琼斯多项式的计算”日本应用数学学会汇刊 8,3（1998）。

今井桂子: "凸多角形の多角形領域内へのmaximin配置問題"地理情報システム学会第3回OOGISワークショップ予稿集. 37-42 (1999)

Keiko Imai：“凸多边形的多边形区域内的最大最小放置问题”地理信息系统协会第三届 OOGIS 研讨会论文集 37-42 (1999)。

桜井裕邦, 今井桂子: "3次元凸多面体上の近似最短経路アルゴリズムの実験的評価"情報処理学会研究報告. 99-AL-67. 47-52 (1999)

Hirokuni Sakurai、Keiko Imai：“三维凸多面体上的近似最短路径算法的实验评估”日本信息处理学会研究报告 99-AL-67（1999）。

K. Sadakane, H. Imai, K. Onishi, M. Inaba, F. Takeuchi and K. Imai: "Voronoi Diagram by Divergences with Additive Weights"Proce. of the Fourteenth Annual Symposium on Computational Geometry. 403-404 (1998)

K. Sadakane、H. Imai、K. Onishi、M. Inaba、F. Takeuchi 和 K. Imai：“带有附加权重的散度的 Voronoi 图”过程。

Kyoko Sekine, Hiroshi Imai and Keiko Imai: "Computation of the Jones Polynomial (in Japanese)"Transactions of the Japan Society for Industrial and Applied Mathematics. Vol.8, No.3. 341-354 (1998)

Kyoko Sekine、Hiroshi Imai 和 Keiko Imai：“琼斯多项式的计算（日语）”日本工业与应用数学学会汇刊。