Size constrained k simple polygons
Aaron Reich, Roxana Ohriniuc, KwangSoo Yang · 2018
Given a geometric space and a set of weighted spatial points, the Size Constrained k Simple Polygons (SCSP) problem identifies k simple polygons that maximize the total weights of the spatial points covered by the polygons and honor the polygon size constraint. The SCSP problem is important for many societal applications, such as 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. This paper proposes a novel approach for finding k simple polygons that maximize the total weights under the size constraint. Experiments using Chicago crime datasets demonstrate that the proposed algorithm outperforms baseline approaches and reduces the computational cost to create a SCSP.