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

作     者：董君 朱恒亮 曾璇 Dong Jun;Zhu Hengliang;Zeng Xuan

作者机构：复旦大学专用集成电路与系统国家重点实验室上海201203 

出 版 物：《计算机辅助设计与图形学学报》 (Journal of Computer-Aided Design & Computer Graphics)

年 卷 期：2014年第26卷第3期

页      面：364-369页

核心收录：

学科分类：081203[工学-计算机应用技术] 08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家重点基础研究发展计划项目(2011CB309701) 国家自然科学基金(61106032 61076033 61125401) 国家十二五科技重大专项项目(2011ZX01034-005-001-03) 上海市领军人才项目 

主　　题：艺术画廊问题 可见多边形 带权值目标点 计算几何 整数线性规划 

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