Combinatorial Aspects of Point Visibility

9304081 Abello这个项目关注的问题是确定给定的图是否是平面上一个简单多边形的可见性图。这个问题已知存在于PSPACE中，但不知道是NP-HARD。事实上，即使证明NP中的隶属性也是不平凡的。基于简单多边形的可见性图可以用对称群的弱Bruhat阶链表示其底层点构型，以纯组合的方式导出，提出了一种研究简单多边形可见性图性质的新方法。其中一个目标是用对称群的弱Bruhat阶链派生出的一类图来描述简单多边形的可见性图。这样的刻画将证明NP中的隶属性，也为可见性图识别问题提供了一种纯组合算法。此外，可视化图识别与计算合成几何中的基本问题（如定向矩阵表示和圆序列实现）之间的组合和算法关系也在研究中。

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.