论文标题
在凸球粉丝和地形的可见度图上
On Visibility Graphs of Convex Fans and Terrains
论文作者
论文摘要
在关闭简单多边形$ p $的两个点时，我们说，如果将它们的线段团结在一起，则它们在$ p $中彼此见面。 $ p $的可见度图是其顶点集的图表，即$ p $的顶点集，如果他们在$ p $中彼此见面，则将两个顶点连接在一起。 数十年来，可见性图的表征一直是一个空旷的问题，并且已经付出了很大的努力来表征受限制多边形类别的可见性图。其中包括凸风扇：具有凸顶顶点的简单多边形（即其内部角度小于180度），可以看到多边形闭合（通常称为kernel顶点）中的每个其他点。我们表明，凸风扇的可见性图等效于地形的可见度图，并添加了通用顶点，即与其他每个顶点相邻的顶点。
For two points in the closure of a simple polygon $P$, we say that they see each other in $P$ if the line segment uniting them does not intersect the exterior of $P$. The visibility graph of $P$ is the graph whose vertex set is the vertex set of $P$ and two vertices are joined by an edge if they see each other in $P$. The characterization of visibility graphs has been an open problem for decades, and a significant effort has been made to characterize visibility graphs of restricted polygon classes. Among them is the convex fan: a simple polygon with a convex vertex (i.e. whose internal angle in less than 180 degrees) that sees every other point in the closure of the polygon (often called kernel vertex). We show that visibility graphs of convex fans are equivalent to visibility graphs of terrains with the addition of a universal vertex, that is, a vertex that is adjacent to every other vertex.
