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.
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.
@cite_27 @cite_15 @cite_17 @cite_2
2045156582 77353308 1673927286 2410099853
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 . 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. Given n points in a circular region C in the plane, we study the problems of moving the n points to the boundary of G to form a regular n-gon such that the maximum (min-max) or the sum (min-sum) of the Euclidean distances traveled by the points is minimized. These problems have applications, e.g., in mobile sensor barrier coverage of wireless sensor networks. The min-max problem further has two versions: the decision version and the optimization version. For the min-max problem, we present an O(nlog2n) time algorithm for the decision version and an O(nlog3n) time algorithm for the optimization version. The previously best algorithms for the two problem versions take O(n3.5) time and O(n3.5logn) time, respectively. For the min-sum problem we show that a special case with all points initially lying on the boundary of the circular region can be solved in O(n2) time, improving a previous O(n4) time solution. For the general min-sum problem, we present a 3-approximation O(n2) time algorithm. In addition, a by-product of our techniques is an algorithm for dynamically maintaining the maximum matching of a circular convex bipartite graph; our algorithm can handle each vertex insertion or deletion on the graph in O(log2n) time. This result may be interesting in its own right. In this paper we provide faster algorithms for solving the geometric median problem: given n points in d compute a point that minimizes the sum of Euclidean distances to the points. This is one of the oldest non-trivial problems in computational geometry yet despite a long history of research the previous fastest running times for computing a (1+є)-approximate geometric median were O(d· n4 3є−8 3) by Chin et. al, O(dexpє−4logє−1) by Badoiu et. al, O(nd+poly(d,є−1)) by Feldman and Langberg, and the polynomial running time of O((nd)O(1)log1 є) by Parrilo and Sturmfels and Xue and Ye. In this paper we show how to compute such an approximate geometric median in time O(ndlog3n є) and O(dє−2). While our O(dє−2) is a fairly straightforward application of stochastic subgradient descent, our O(ndlog3n є) time algorithm is a novel long step interior point method. We start with a simple O((nd)O(1)log1 є) time interior point method and show how to improve it, ultimately building an algorithm that is quite non-standard from the perspective of interior point literature. Our result is one of few cases of outperforming standard interior point theory. Furthermore, it is the only case we know of where interior point methods yield a nearly linear time algorithm for a canonical optimization problem that traditionally requires superlinear time.