Studies of Geometric Algorithms and Their Applicatins

在过去的几年里，计算几何这一相对较新的领域以加速的速度发展。它包含的问题涵盖了广泛的应用，如运动规划和计算机图形学，它们的解决方案往往涉及到使用从数学和理论计算机科学的许多分支中提取的复杂技术。以前的工作包括对该领域的许多基本和应用问题的广泛贡献，包括运动规划、隐面去除和相关的可见性问题、曲线和代数曲面排列的组合和代数分析、线性规划的随机化算法和其他优化问题等。本研究的目的是继续在这些领域的工作并将其扩展到计算几何的新的核心领域。研究的主要部分致力于研究曲线和曲面的排列。具体地说，正在研究以下问题：1.与子结构(下包络、单单元、区域等)相关的组合和算法问题。在更高维度的表面的排列中。2.半代数集单元和道路图计算的实代数几何中的相关算法。3.涉及线段或曲线的平面排列的组合和算法问题(也称为“几何图形”)。在这项工作中明显的一个主题是计算几何的基础研究和各种应用领域之间的丰富交叉，其中一个领域的问题激发了对新的基本问题的研究，其解决方案反过来又在许多其他领域找到应用。另一个主题是排列中子结构的组合分析与设计相应的高效算法来构造和利用这些结构之间的密切联系。通常，这种算法的效率关键取决于要计算的结构的大小，而大多数算法设计都必须致力于对该结构的复杂性进行组合分析。这些考虑反映在正在进行的工作中。

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.