Combinatorial Methods for Discrete Geometry

在这个项目中，我们首先从离散几何和分类中提取了一系列问题的组合方面。然后，根据每个类别，我们尝试建立一种适合离散几何的一般方法。以下是这个项目中最成功的结果中的一些。在离散的几何学中，有许多问题，它们基本上等同于直线段的连接点，因此，结果的几何对象将成为一个汉密尔顿循环嵌入在平面上，这是跨越直线段的最少数目。我们提出了他们在本质中的组合问题，并建立了一个组合方法来解决它们。我们已经提出了一种独立的几何树的问题，它可以被处理成一种扩展到图形中的独立树，并且我们已经找到了一种图形理论方法来处理这些问题。在一个离散的几何空间中，有许多问题来划分一个欧几里得空间，其中一个极小数量的几何物体由一个超平面组成，所以两个分隔的半空间都包含着几乎相同数量的物体。我们研究了这些问题的综合方面，并在每个物体中解决了这些问题。我们已经提出了在离散几何中存在许多问题，其中一些是基本的图形分解问题。我们解决了许多这些分解问题，特别是在完整的图形和完整的双字节图形的情况下，上面的结果只是我们的部分结果的一小部分，在项目报告中完全描述。考虑到结果的质量，我们相信这个项目是非常成功的。

In this project, we first extracted the combinatorial aspects from a number of problems in discrete geometry, and categorized them. Then by invetigating each category, we tried to establish general methods which are applicable to discrete geometry. The following are some of the most successful results in this project.・ In discrete geometry, there are a number of problems which are essentially equivalent to joining points by straight line segments so that the resulting geometric object becomes a hamiltonian cycle embedded in the plane and that it has the least number of crossing of line segments. We proved that they are combinatorial problems in essence, and established a combinatorial method to tackle them.・ We proved that the problems of independent geometric trees can be handled as an extension of independent trees in graphs, and we establlished a graph-theoretic approach to address these problems.・ In discrete geomtery, there are many problems on dividing an Euclidean space with a finite number of geometric objects by a hyperplane so that both divided half-spaces contain almost the same number of the objects. We studied the combinatorial aspects of these problems, and solved the problem in which each object is a ball.・ We proved that there are many problems in discrete geometry which are essentially graph decomposition problems. We solved a number of these decomposition problems, especially in case of complete graphs and complete bipartite graphs.The above results are just a small fraction of our entire results, which are described fully in the project report. Considering the quantity of the quality of the result, we believe that this project was extremely successful.