Geometric Knapsack problems (Q689105)

We study a variety of geometric versions of the classical knapsack problem. In particular, we consider the following ``fence enclosure'' problem: Given a set \(S\) of \(n\) points in the plane with values \(v_ i\geq 0\), we wish to enclose a subset of the points with a fence (a simple closed curve) in order to maximize the ``value'' of the enclosure. The value of the enclosure is defined to be the sum of the values of the enclosed points minus the cost of the fence. We consider various versions of the problem, and give the following results: (1) We show that when the values \(v_ i\) are unrestricted in sign, the minimum-length enclosure problem is \(NP\)-hard. (2) We show that when there is an upper bound on the perimeter or the area of the allowed enclosure, then the problem of enclosing a maximum- value subset of points with values \(v_ i>0\) is \(NP\)-hard. We provide a pseudo-polynomial algorithm for the case in which all the values \(v_ i\) are integral. This also allows us to solve the following: Find the smallest perimeter (or area) polygon that encloses \(k\) points of a set of \(n\) points \(S\). Our solutions requires time \(O(kn^ 3)\) and space \(O(kn^ 2)\). (3) If \(v_ i>0\) and there is no bound on the length of fence available but there is a cost \(c>0\) per unit length of fence, we solve various versions of the optimal single \((M=1)\) enclosure problem in polynomial time. The objective function that we are to maximize is defined as the sum of the values of the objects enclosed minus the cost of the fence. (a) For the case of enclosing \(n\) points, we give an \(O(n^ 3)\) times algorithm. (b) For the case in which \(S\) is a set of simple polygonal objects, and objects have to be either entirely included or entirely excluded, we give an \(O(en^ 2)\) algorithm, where \(e=O(n^ 2)\) is the size of the visibility graph of \(S\). If instead, we are allowed to build fences through the polygons \(S\), but only receive value according to the fraction of the area of an object we enclose, we obtain an \(O(n^ 3)\) time algorithm. (4) We give a polynomial-time algorithm for the multiple-fence point enclosure problem, for fixed number of fences.