Research on Algorithms for Discrete Geometric Structures

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

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.