Geometric Complexity Problems in Arrangements

排列中的几何复杂性问题

• 批准号: 9211541
• 负责人: Boris Aronov
• 金额: $ 7.25万
• 依托单位: Polytechnic University of New York
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1992
• 资助国家: 美国
• 起止时间: 1992-07-01 至 1996-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9211541&HistoricalAwards=false
• 关键词: Geometric; Complexity; Problems; Arrangements

Computational Geometry is primarily the study of geometric algorithms. Thus the geometric aspect of problems considered by computational geometers is as important as the algorithm and data structuring aspect. Sometimes the connection is explicit, e.g, when the number of features of a geometric object provides a worst-case lower bound on the running time to compute it. Other times the relation is less obvious, but just as crucial. This project is concerned with geometric arrangements from a primarily combinatorial rather than computational point of view, with investigation of algorithmic issues as a secondary goal. The focus is on the geometric complexity problems, which involve estimating the number of features in certain portions of an arrangement. Such combinatorial bounds lead to construction of efficient geometric algorithms and to establishing sharp lower bounds on their performance. Planar arrangements of various classes of objects and general hyperplane arrangements have been studied extensively, but until recently rather little was known about arrangements of such simple objects as flat triangles in three-dimensional space. Building on some recent work, the investigation of this subject will be continued, initially concentrating on triangle arrangements. The study of simplex arrangements is expected to lead to new techniques applicable to more general families of objects in three and higher dimensions, which will in turn yield better tools for the design and analysis of geometric algorithms.

计算几何主要是研究几何 算法 因此，所考虑的问题的几何方面 计算几何学家的方法和算法一样重要 数据结构方面。 有时候这种联系 明确的，例如，当几何图形的特征数量 对象提供了运行时间的最坏情况下限 其他时候这种关系不那么明显，但是 同样重要。 这个项目是关于几何安排从一个 主要是组合而不是计算点， 视图，其次是对算法问题的调查 目标. 重点是几何复杂性问题， 这涉及到估计某些特征的数量， 安排的一部分。 这样的组合界限导致 构造高效的几何算法， 建立了他们的业绩的急剧下降。 各类物体的平面排列和一般 超平面排列已经被广泛研究，但是 直到最近，人们对这种安排知之甚少。 像平面三角形这样简单的物体 空间 根据最近的一些工作， 本主题将继续，最初集中于 三角形排列 单纯形排列的研究是 预计将导致适用于更普遍的新技术 三维或更高维度的物体家族， 反过来又为设计和分析提供了更好的工具， 几何算法