Understanding Geometric Arrangements: Unions and Beyond

单位：纽约理工大学kpi: Aronov， boris题目：理解几何排列：并集及其以外摘要本研究集中在一类涉及物体并集的几何问题上。组合几何和计算几何中许多被广泛研究的问题都可以用这些术语来表达。在研究组合学和算法之间联系的重要经验的基础上，研究人员探索在对象联合问题中出现的组合问题，以开发新的、简单的、强大的组合工具，并改进现有的组合工具。细化迄今为止开发的技术，工作扩展了问题的范围，以涵盖对象覆盖的优化问题。在整个调查过程中，研究人员强调了以下主题：开发新的，更强大的工具来处理组合问题。发现对“经典”问题的更简单的证明和简化的方法，使研究结果对学生和非专业人士来说更容易获得，并最终与其声称的受益者，即应用领域的从业者更相关。此外，它们很可能促进该领域的进一步进展。

Proposal: CCF- 0830691Institution: Polytechnic University of New YorkPI: Aronov, BorisTitle: Understanding Geometric Arrangements: Unions and Beyond ABSTRACTThe research centers on a class of geometric problems involving unions of objects. A variety of much-studied problems in combinatorial and computational geometry can be cast in these terms. Building on significant previous experience investigating the connections between combinatorics and algorithmics, the investigators explore combinatorial problems arising in the union-of-objects questions in order to develop new, simple, and powerful combinatorial tools and to refine those already available. Refining the techniques developed so far, the work expands the scope of problems to encompass questions of optimization in overlays of objects.Throughout the investigation, the researchers emphasize the following theme: Developing new, more powerful tools for dealing with combinatorial problems. Discovery of easier proofs of and streamlined approaches to ``classical'' problems makes research results significantly more accessible to students and non-specialists and ultimately more relevant to its claimed beneficiaries, the practitioners in the application areas. Moreover, they are very likely to foster further progress in the field.