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。

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.