Size constrained k simple polygons
Size constrained k simple polygons
复制标题
DOI：
10.1007/s10707-020-00416-9
复制
发表时间：
2020-07
期刊：
影响因子：
2
通讯作者：
Kwangsoo Yang;Kwang Woo Nam;Ahmad Qutbuddin;Aaron Reich;Valmer Huhn
中科院分区：
文献类型：
--
作者：
Kwangsoo Yang;Kwang Woo Nam;Ahmad Qutbuddin;Aaron Reich;Valmer Huhn
给定一个几何空间和一组加权空间点，大小约束k个简单多边形（SCkSP）问题识别出k个简单多边形，这些简单多边形所覆盖的空间点的总权重最大化，并满足多边形的大小约束。SCkSP问题对于热点区域检测和资源分配等许多社会应用具有重要意义。这个问题是np困难的；由于大量的空间点和多边形尺寸的限制，它在计算上具有挑战性。我们的初步工作为SCkSP引入了最近邻三角剖分和合并（NNTM）算法，以满足空间点的大小约束，同时最大化空间点的总权重。然而，我们发现NNTM算法的性能依赖于最近图。在本文中，我们扩展了我们之前的工作，并提出了一种优于我们之前工作的新方法。使用芝加哥犯罪和美国联邦野火数据集进行的实验表明，所提出的算法显著降低了我们之前工作的计算成本，并产生了更好的解决方案。
Given a geometric space and a set of weighted spatial points, the Size Constrained k Simple Polygons (SCkSP) problem identifiesksimple polygons that maximize the total weights of the spatial points covered by the polygons and meet the polygon size constraint. The SCkSP problem is important for many societal applications including hotspot area detection and resource allocation. The problem is NP-hard; it is computationally challenging because of the large number of spatial points and the polygon size constraint. Our preliminary work introduced the Nearest Neighbor Triangulation and Merging (NNTM) algorithm for SCkSP to meet the size constraint while maximizing the total weights of the spatial points. However, we find that the performance of the NNTM algorithm is dependent on thet-nearest graph. In this paper, we extend our previous work and propose a novel approach that outperforms our prior work. Experiments using Chicago crime and U.S. Federal wildfire datasets demonstrate that the proposed algorithm significantly reduces the computational cost of our prior work and produces a better solution.