RUI: Geometric Intersection Graphs

该项目设想了两个主要目标：首先，它研究图形的几何表示理论，建立在广泛的数学方法基础上，并将结果整合到新技术中。其次，它培养下一代学生在数学，科学和工程的职业生涯，专注于离散数学的坚实基础，并发展数学技能，有效地处理几何对象。可视化复杂系统和大型数据集已成为常规，包括用户友好地处理低维虚拟对象。在这种情况下，设计有效的计算机工具是一项具有挑战性的任务，它需要对几何对象及其之间的关系如何表示的透彻理解，以及熟悉这些数学工具的能力和局限性的高素质开发人员和科学家。拓扑约束通常由曲线或曲面的交图中不可避免的模式捕获，并且与组合几何中的Ramsey型结果密切相关。度量约束对应于可以同时实现的距离、斜率、角度和面积的模式。当边用代数曲线（包括直线）表示时，代数约束起着重要的作用。这个项目将研究几何对象的相交模式，其中相交关系由无向图表示，它还将研究几何图，拓扑图，超图或单纯复形嵌入到低维欧氏空间中所产生的相交。相关的枚举问题将被考虑，以及度量和拓扑约束与经典的组合问题相结合，产生新的挑战。基本几何对象（如点、线段、直线和二次曲面）的实现空间的定量界限在制图学、计算机科学、优化和实体建模中有应用。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估来支持。

This project envisions two main objectives: First, it studies the theory of geometric representations of graphs, building on a broad array of mathematical methods, and integrating the results into new technology. Second, it trains the next generation of students for careers in mathematics, sciences, and engineering, focusing on solid foundations in discrete mathematics, and developing mathematical skills for handling geometric objects efficiently. Visualizing complex systems and large data sets has become routine, including user-friendly handling of virtual objects in low dimensions. Designing efficient computer tools in this context is a challenging task, it calls for a thorough understanding of how geometric objects and relations between them are represented, as well as highly qualified developers and scientists who are familiar with the capabilities and limitations of these mathematical tools.Representing graphs in space is constrained by topological, metric, and algebraic properties. Topological constraints are typically captured by unavoidable patterns in the intersection graph of curves or surfaces, and is closely related to Ramsey-type results in combinatorial geometry. Metric constraints correspond to patterns in distances, slopes, angles, and areas that can be realized simultaneously. Algebraic constraints play an important role when edges are represented by algebraic curves (including straight lines). This project will study the intersection patterns of geometric objects, where the intersection relation is represented by an undirected graph, and it will also examine the intersections created by embeddings of geometric graphs, topological graphs, hypergraphs, or simplicial complexes into Euclidean spaces of low dimensions. Related enumerative problems will be considered, as well, where metric and topological constraints combined with classical combinatorial problems yield new challenges. Quantitative bounds for the realization spaces of basic geometric objects (such as points, line segments, lines, and quadrics) have applications in cartography, computer science, optimization, and solid modelling.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.