带权值目标点的可见覆盖求解算法

• 作者: 曾璇 朱恒亮 董君
• 来源期刊: 计算机辅助设计与图形学学报
• 学科: 工学
• 关键词: 艺术画廊问题 可见多边形 带权值目标点 计算几何 整数线性规划
• 年，卷（期）: 2014,（3）
• 所属期刊栏目: 图形与可视化
• 页码范围: 364-369
• 页数: 6页
• 分类号: TP391
• 字数: 4619字
• 语种: 中文

摘要

针对传统的艺术画廊模型及其模型的变形在实际应用中无法处理诸如可用守卫数受限、只需监控离散目标点等情形,提出一种基于带权值目标点的可见覆盖的变形模型及其求解算法.首先利用角扫描技术得到每个目标点的可见多边形,然后通过对这些可见多边形进行几何求交、几何求差操作来得到若干等价目标可见区域,再依据每个区域对应的可见目标点集将所提出的变形模型转化为经典的集合最大权值覆盖问题,最后利用整数线性规划方法对其求解,得到最终需要的守卫数及放置位置.大量的实验结果表明,该算法是正确和有效的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	曾璇	复旦大学专用集成电路与系统国家重点实验室	34	66	4.0	6.0
2	董君	复旦大学专用集成电路与系统国家重点实验室	6	51	3.0	6.0
3	朱恒亮	复旦大学专用集成电路与系统国家重点实验室	7	8	1.0	2.0