Covering a Set of Points with k Bounding Boxes Covering a set of points with  k  orthogonal bounding boxes is useful for implementing spatiotemporal index structures that are built from a given dataset. In this work we deal with the problem of covering a set of points with kparallel 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 kbounding boxes where the total sum of the areas of the boxes is minimum. This is compared with the process of generating kbounding boxes every  l  units of distance, achieving an improvement of about 50% of unuseful area covered.

Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack The area of parameterized approximation seeks to combine approximation and parameterized algorithms to obtain, e.g., (1eps)approximations in f(k,eps)nO(1) time where k is some parameter of the input. We obtain the following results on parameterized approximability: 1) In the maximum independent set of rectangles problem (MISR) we are given a collection of n axis parallel rectangles in the plane. Our goal is to select a maximumcardinality subset of pairwise nonoverlapping rectangles. This problem is NPhard and also W1hard Marx, ESAu002705. The bestknown polynomialtime approximation factor is O(loglog n) Chalermsook and Chuzhoy, SODAu002709 and it admits a QPTAS Adamaszek and Wiese, FOCSu002713; Chuzhoy and Ene, FOCSu002716. Here we present a parameterized approximation scheme (PAS) for MISR, i.e. an algorithm that, for any given constant epsu003e0 and integer ku003e0, in time f(k,eps)ng(eps), either outputs a solution of size at least k(1eps), or declares that the optimum solution has size less than k. 2) In the (2dimensional) geometric knapsack problem (TDK) we are given an axisaligned square knapsack and a collection of axisaligned rectangles in the plane (items). Our goal is to translate a maximum cardinality subset of items into the knapsack so that the selected items do not overlap. In the version of TDK with rotations (TDKR), we are allowed to rotate items by 90 degrees. Both variants are NPhard, and the bestknown polynomialtime approximation factors are 558325eps and 43eps, resp. Galvez et al., FOCSu002717. These problems admit a QPTAS for polynomially bounded item sizes Adamaszek and Wiese, SODAu002715. We show that both variants are W1hard. Furthermore, we present a PAS for TDKR. For all considered problems, getting time f(k,eps)nO(1), rather than f(k,eps)ng(eps), would give FPT time fu0027(k)nO(1) exact algorithms using eps1(k1), contradicting W1hardness.