Studies of Geometric Algorithms and Their Applicatins

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

The relatively new field of computational geometry has developed at an accelerating rate in the past few years. The problems that it encompasses cover a wide range of applications, such as motion planning and computer graphics, and their solution often involves the use of sophisticated techniques drawn from many branches of mathematics and theoretical computer science. Prior work includes extensive contributions to many basic and applied problems in the area, including motion planning, hidden surface removal and related visibility problems, combinatorial and algebraic analysis of arrangements of curves and algebraic surfaces, randomized algorithms for linear programming and other optimization problems, etc. The purpose of this research is to continue the work in these fields and to extend it into new core areas in computational geometry. A major portion of the research is devoted to the study of arrangements of curves and surfaces. Specifically, the following problems are being studied: 1. Combinatorial and algorithmic problems related to substructures (lower envelopes, single cells, zones, etc.) in arrangements of surfaces in higher dimensions. 2. Related algorithms in real algebraic geometry for computing cells and road maps in semi-algebraic sets. 3. Combinatorial and algorithmic problems involving planar arrangements of segments or curves (also known as ``geometric graphs''. A theme that is manifest in this work is the rich cross-fertilization between basic research in computational geometry and the various application areas, where problems in one area motivate the study of new basic problems whose solution in turn finds applications in many other areas. Another theme is the strong connection between the combinatorial analysis of substructures in arrangements and the design of corresponding efficient algorithms for constructing and utilizing these structures. Often the efficiency of such an algorithm crucially depends on the size of the structure to be computed, and most of the algorithm design has to be devoted to the combinatorial analysis of the complexity of that structure. These considerations are reflected in the work being done.