text: We consider discretization of the 'geometric cover problem' in the plane: Given a set @math of @math points in the plane and a compact planar object @math , find a minimum cardinality collection of planar translates of @math such that the union of the translates in the collection contains all the points in @math . We show that the geometric cover problem can be converted to a form of the geometric set cover, which has a given finite-size collection of translates rather than the infinite continuous solution space of the former. We propose a reduced finite solution space that consists of distinct canonical translates and present polynomial algorithms to find the reduce solution space for disks, convex non-convex polygons (including holes), and planar objects consisting of finite Jordan curves.
  @cite_27: 
  @cite_15: We present an efficient algorithm for solving the “smallest k-enclosing circle” (kSC) problem: Given a set of n points in the plane and an integer k ≤ n, find the smallest disk containing k of the points. We resent several algorithms that run in O(nk logcn) time, where the constant c depends on the storage that the algorithm is allowed. When using O(nk) storage, the problem can be solved in time O(nk log2n). When only O(n log n) storage is allowed, the running time is O(nk log2n log n k.). The method we describe can be easily extended to obtain efficient solutions of several related problems (with similar time and storage bounds). These related problems include: finding the smallest homothetic copy of a given convex polygon P, which contains k points from a given planar set, and finding the smallest hypodrome of a given length and orientation (formally defined in Section 4) containing k points from a given planar set.
  @cite_17: Abstract Given a set S of n points in the plane and a convex polygon P with m vertices, we consider the problem of finding a translation of P that contains the maximum number of points in S . We present two different solutions. Our first algorithm uses standard line-sweep techniques and requires O( nk log( nm ) + m ) time where k is the maximum number of points contained. Our second algorithm requires O( nk log( mk ) + m ) time, which is the asymptotically fastest known algorithm for this problem. Both algorithms require optimal O( m + n ) space. The algorithms also solve in the same running time the bichromatic variant of the problem, where we are given two point sets A and B and the goal is to maximize the number of points covered from A while minimizing the number of points covered from B .
  @cite_2: We consider the following circle placement problem: given a set of pointsp i ,i=1,2, ...,n, each of weightw i , in the plane, and a fixed disk of radiusr, find a location to place the disk such that the total weight of the points covered by the disk is maximized. The problem is equivalent to the so-called maximum weighted clique problem for circle intersection graphs. That is, given a setS ofn circles,D i ,i=1,2, ...,n, of the same radiusr, each of weightw i , find a subset ofS whose common intersection is nonempty and whose total weight is maximum. AnO (n2) algorithm is presented for the maximum clique problem. The algorithm is better than a previously known algorithm which is based on sorting and runs inO (n2 logn) time.
summary: Given a set @math of @math points in the plane, the optimal placement problem is to compute a translate that contains the maximum number of points in @math ; note that in our problem, the distinct canonical translates contain the points of @math in a locally maximal manner (see Definition ). There are some optimal placement algorithms for basic planar objects: Chazelle and Lee @cite_2 presented @math time algorithm for disks, and Eppstein and Erickson @cite_27 proposed @math time algorithm for rectangles; for convex polygons of @math vertices, @cite_15 devised @math time algorithm, and @cite_17 improved the time complexity to @math , where @math is the maximum number of points in @math that can be contained in a translate.