计算几何, 算法分析
在一个所谓的 “矩形多边形” (rectilinear polygon)中, 所有边的方向不是水平的就是垂直的. 考察包含 n个顶点的矩形多边形 p. 试举例说明: 为了看守这种多边形, 有时至少需要n/4台摄像机.
请给点意见吧?
[解决办法]
很简单，举个例子，就是正方形，它是Rectilinear polygon的一种，有4个顶点(n=4)，要看守他（放m台摄像机使得正方形内部每个点都能被摄像机看到），至少需要1台摄像机，而1==n/4
[解决办法]
昨天晚上想回答这个问题,被老婆强制去睡觉了,所以话没说清楚.
1,平面多边形三角化,这个资料很多,自己去搜一下看看,就是把多边形变成三角形组成的集合.
2,然后用三种色染色顶点,每个相邻的点都不用同一颜色.
(由三角形构成的多边形,最多三种颜色搞定,有定理的)
3,然后选其中一种颜色作为摄象机(卫兵/灯泡)
http://academic.research.microsoft.com/Paper/271274.aspx?query=star-shaped
这篇文章你可以看看,是把一个空心汉字"至"字分解成星形多边形的.
这类问题和矩形多边形没关系,也许矩形多边形有更快更好的解法.
不要自己花太长时间思考了,多搜一下,借鉴前人的结论.
我一般是用自己做的多线程搜论文工具(目前想把它做的更强公布出来给大家用),
先就一个关键词,下一堆文章,然后迅速判断哪个有用哪个没用,再研究有用的.
