Research on Algorithms for Discrete Geometric Structures

点击翻译按钮获取中文摘要

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.