Combinatorial Aspects of Point Visibility

点可见性的组合方面

• 批准号: 9304081
• 负责人: James Abello
• 金额: $ 3.96万
• 依托单位: Texas A&M Engineering Experiment Station
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1993
• 资助国家: 美国
• 起止时间: 1993-08-01 至 1995-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9304081&HistoricalAwards=false
• 关键词: Combinatorial; Aspects; Point; Visibility

9304081 Abello This project is concerned with the problem of deciding if a given graph is the visibility graph of a simple polygon on the plane. This problem is known to be in PSPACE but it is not known to be NP-HARD. In fact even proving membership in NP appears to be non trivial. A novel approach to studying properties of visibility graphs of simple polygons is being pursued based on the result that visibility graphs of simple polygons can be derived in a purely combinatorial manner from the representations of their underlying point configurations by chains in the weak Bruhat order of the symmetric group. One of the objectives is to obtain a characterization of visibility graphs of simple polygons in terms of a class of graphs derived from chains in the weak Bruhat order of the symmetric group. Such a characterization would prove membership in NP and also provide a purely combinatorial algorithm for the visibility graph recognition problem. In addition, the combinatorial and algorithmic relationships between visibility graph recognition and fundamental problems in Computational Synthetic geometry, such as oriented matroid representation and circular sequence realization are being explored.

9304081阿贝罗这个项目是关于判断一个给定的图是否为平面上一个简单多边形可见性图的问题。这个问题已知存在于PSPACE中，但还不知道它是NP难的。事实上，即使是证明NP的成员身份似乎也不是一件微不足道的事情。研究简单多边形可见性图的一种新方法是基于这样的结果，即简单多边形可见性图可以通过对称群的弱Bruhat阶链对其下层点构型的表示以纯组合的方式得到。其中一个目的是利用对称群的弱Bruhat阶链导出的一类图来刻画简单多边形可见性图。这样的刻画将证明在NP中的成员关系，也为可见性图识别问题提供了一个纯粹的组合算法。此外，还探讨了可见性图形识别与计算综合几何中的基本问题，如定向拟阵表示和循环序列实现之间的组合和算法关系。