Research on Algorithms for Discrete Geometric Problems under Dynamic Environments

动态环境下离散几何问题的算法研究

• 批准号: 08650081
• 负责人: IMAI Keiko
• 金额: $ 1.28万
• 依托单位: CHUO UNIVERSITY
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 1996
• 资助国家: 日本
• 起止时间: 1996 至 1997
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-08650081/
• 关键词: Discrete structures; Enumeration algorithm; Computational geometry; Triangulation

The aim of this research is to develop efficient algorithms for discrete problems with geometric information under dynamic environments. Many practical problems have dynamic 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 factors and geometric structures.First, we mainly focus on enumeration problems of triangulations. To handle dynamical changes for geometric structures, we have to consider enumerating all possible structures and combinatorial problems. Triangulation is one of the fundamental concepts in computational geometry, and useful for many applications, and we developed an output-size sensitive and work-space efficient algorithm for enumerating regular triangulations by reverse search. Regular triangulation from a meaningful wide subclass of triangulations of points in general dimensions.Also, we consider the problem of computing a minimum weight triangulation, which has been intensively studied in recent years in computational geometry. The problem can be formulated as finding a minimum-weight maximal independent set of intersection graphs of edges. Combining the branch-and-cut approach with the beta-skeleton method, the moderate-size problem could be solved efficiently in our computational experiments.Efficient algorithms have been developed for enumeration of regular triangulations and computing a minimum weight triangulation. Under dynamic environments, considering network reliability is important. Therefore, network reliability computation, computation of invariant polynomials in computational algebra and computational geometry have been investigated in this research.

本研究的目的是发展动态环境下具有几何信息的离散问题的有效算法。许多实际问题具有动态性质，这些离散结构包含几何信息。对于静态离散问题，已经研究了许多有效的结果。然而，需要重新设计算法来处理动态因素和几何结构。首先，我们主要关注三角测量的枚举问题。为了处理几何结构的动态变化，我们必须考虑列举所有可能的结构和组合问题。三角剖分是计算几何中的一个基本概念，在许多应用中都很有用，我们开发了一种输出大小敏感和工作空间高效的算法，用于通过反向搜索枚举规则三角剖分。一般维点的三角剖分的一个有意义的广义子类的正则三角剖分。此外，我们还考虑了计算最小权值三角剖分的问题，该问题近年来在计算几何中得到了广泛的研究。这个问题可以表述为寻找一个最小权值最大的独立的边相交图集。将支切法与β -骨架法相结合，可以有效地解决中等尺寸问题。对于规则三角测量的枚举和最小权值三角测量的计算，已经开发出了有效的算法。在动态环境下，考虑网络的可靠性是很重要的。因此，本文研究了网络可靠性计算、计算代数和计算几何中不变多项式的计算。

项目成果

Keiko Imai: "Enumeration of Regular Triangulations" 数理解析研究所講究録. 950. 126-132 (1996)

Keiko Imai：“正则三角剖分的枚举”数学科学研究所 Kokyuroku。950. 126-132 (1996)

K.Imai and H.Imai: "Enumeration of Regular Triangulations." RIMS Kokyuroku 950, Kyoto University. 126-132 (1996)

K.Imai 和 H.Imai：“规则三角剖分的枚举”。

T.Ono, Y.Kyoda, T.Masada, K.Hayase, T.Shibuya, M.Nakade, M.Inaba, H.Imai, K.Imai and D.Avis: "A Package for Triangulations." Proceedings of the 12th Annual ACM Symposium on Computational Geometry, Video descriptions.V17-V18 (1996)

T.Ono、Y.Kyoda、T.Masada、K.Hayase、T.Shibuya、M.Nakade、M.Inaba、H.Imai、K.Imai 和 D.Avis：“三角测量包”。

K.Okada and K.Imai: "Experimental results for Learning of Geometric Concepts in PAC Model." Discrete and computational Geometry Workshop 97. 75-79

K.Okada 和 K.Imai：“PAC 模型中几何概念学习的实验结果”。

Y.Kyoda, K.Imai, F.Takeuchi and A.Tajima: "A Branch-and-Cut Approach for Minimum Weight Triangulation." Algorithms and Computation, Lecture Notes in Computer Science. 1350. 384-393 (1997)

Y.Kyoda、K.Imai、F.Takeuchi 和 A.Tajima：“最小权重三角剖分的分支割法”。