|
|
Rn中的集合S称为星形域(star domain)或星形凸集(star convex set),如果存在S中的点$x_{0}$,使得对于S中的所有x,从$x_{0}$到x的线段位于S内。
直观上,如果我们把S视为用围墙包围的一个区域,那么S是一个星形域,当且仅当我们可以在S中找到一个视点$x_{0}$,使得S中的任何点x都在该点的视线内.
如果一个多边形内部是星形域,就称它为星形多边形.
视点z的集合称为星形域的核(图中褐色区域).
多边形的每条边都定义了一个内半平面,其边界位于包含边的直线上,并且包含『在「这条边上的点」附近的「多边形内部的点」』.多边形的核是其所有内半平面的交集.
例子:
环形不是星形域.
一条直线或一个平面去掉一个点不是星形域.
如果A是Rn中的一个集合,那么把A的任何点与原点相连得到的集合$B=\{ta:a\in A,t\in [0,1]\}$是一个星形域.
任何非空凸集都是星形域但星形域不一定是凸集,例如十字形状是星形域,但不是凸集.
性质:
一个星形域的闭包也是星形域,但一个星形域的内部不一定是星形域.
任何星形域都是单连通集合.
两个星形域的并集和交集不一定是星形域.
多边形内两点之间的折线距离(link distance)是以两点为端点的折线的节数的最小值.多边形的折线直径是其内部任意两个点的折线距离的最大值.
一个多边形是凸多边形当且仅当它的折线直径为1.星形多边形的折线直径≤2:对于两个点u,v可以将u连接到视点z再连接到v.然而,满足这个性质的多边形并不一定是星形多边形,因为也存在具有孔洞的多边形,其折线直径为2.
美术馆问题来源于现实世界中的问题:如何用最少的守卫看守美术馆,并使得美术馆的每个角落都在守卫的视野之中.美术馆的形状被表示为一个简单多边形并且每个守卫被表示为该多边形内的一个点.称一个点集S能够守卫一个多边形,如果对多边形内的每个点p,存在点$q\in S$使得连接p和q的线段在多边形的内部.一个等价的问题是: 需要多少盏灯来完全照亮整个房间.
Chvátal美术馆定理给出了一个守卫最少数量的一个上界:
$\left\lfloor \frac n3\right\rfloor $个守卫足够监视一个简单n边形.
证明:(Fisk)
首先,将用多边形内互不相交的对角线将多边形三角化.然后用三种不同的颜色对多边形的顶点上色,使得多边形内的每个三角形的都含有涂有不同颜色的顶点.这可以通过选定一个三角形对它的顶点涂以不同的颜色,将其扩展到与其相邻的三角形具有唯一的方案.由于三角化的对偶图是一个树,我们可以继续下去直至所有的顶点被涂色.在其中的任何一种颜色的全部顶点上放置守卫就可以监视整个多边形:假设使用红,黄,蓝三种颜色,守卫被放置在所有红色的顶点上,由于每个三角形都有一个红色的顶点,并且在这个顶点上可以监视整个三角形,这样所有的三角形都在守卫的监视之中.
https://zh.wikipedia.org/wiki/%E6%98%9F%E5%BD%A2%E5%9F%9F
https://zh.wikipedia.org/wiki/%E7%BE%8E%E6%9C%AF%E9%A6%86%E9%97%AE%E9%A2%98 |
|
