Covering a Set of Points with k Bounding Boxes

Covering a set of points with k orthogonal bounding boxes is useful for implementing spatio-temporal index structures that are built from a given dataset. In this work we deal with the problem of covering a set of points with k-parallel axis boxes, under the restriction that the total area enclosed by the boxes must be minimized. To achieve this, we present a novel algorithm that, using dynamic programming techniques, finds the optimal solution for covering a set of points with k-bounding boxes where the total sum of the areas of the boxes is minimum. This is compared with the process of generating k-bounding boxes every l units of distance, achieving an improvement of about 50% of unuseful area covered.