Combinatorial Aspects of Point Visibility

9304081 Abello这个项目关注的是决定给定图是否是平面上简单多边形的可见性图的问题。 这个问题是已知的PSPACE，但它不是已知的NP-难。 事实上，即使证明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.