Research on Algorithms for Discrete Geometric Problems under Dynamic Environments

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

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.