The Maximum Weight Independent Set of Polygons problem is a fundamental problem in computational geometry. Given a set of weighted polygons in the 2-dimensional plane, the goal is to find a set of pairwise non-overlapping polygons with maximum total weight. Due to its wide range of applications, the MWISP problem and its special cases have been extensively studied both in the approximation algorithms and the computational geometry community. Despite a lot of research, its general case is not well-understood. Currently the best known polynomial time algorithm achieves an approximation ratio of n^(epsilon) [Fox and Pach, SODA 2011], and it is not even clear whether the problem is APX-hard. We present a (1+epsilon)-approximation algorithm, assuming that each polygon in the input has at most a polylogarithmic number of vertices. Our algorithm has quasi-polynomial running time. We use a recently introduced framework for approximating maximum weight independent set in geometric intersection graphs. The framework has been used to construct a QPTAS in the much simpler case of axis-parallel rectangles. We extend it in two ways, to adapt it to our much more general setting. First, we show that its technical core can be reduced to the case when all input polygons are triangles. Secondly, we replace its key technical ingredient which is a method to partition the plane using only few edges such that the objects stemming from the optimal solution are evenly distributed among the resulting faces and each object is intersected only a few times. Our new procedure for this task is not more complex than the original one, and it can handle the arising difficulties due to the arbitrary angles of the polygons. Note that already this obstacle makes the known analysis for the above framework fail. Also, in general it is not well understood how to handle this difficulty by efficient approximation algorithms.
There is a lot of research on the maximum independent set problem for geometric shapes in the plane. For the case when all shapes are unit disks (i.e., the resulting intersection graph is a unit disk graph), polynomial time approximation schemes have been presented by Hunt @cite_10 , and by Hochbaum and Maass @cite_0 . Subsequently, Nieberg, Hurink, and Kern @cite_1 presented a PTAS that does not even need the geometric representation of the graph. Observe here that it is @math -hard to decide whether a given graph is a unit disk graph @cite_11 . Using the geometric embedding, Erlebach, Jansen, and Seidel presented a PTAS for disks with arbitrary diameters, which generalizes to arbitrary fat objects @cite_3 .
@cite_1 @cite_3 @cite_0 @cite_10 @cite_11
2094511120 2154745646 2012427196 2054505111 2018541722 2046479033 2063572899 2084266654 1998375208 1982378203 1510609119 2144614313 2272045681 2060662766 2104589295 77353308 2038964811 2063120809 1549878614 2049981393
A disk graph is the intersection graph of a set of disks with arbitrary diameters in the plane. For the case that the disk representation is given, we present polynomial-time approximation schemes (PTASs) for the maximum weight independent set problem (selecting disjoint disks of maximum total weight) and for the minimum weight vertex cover problem in disk graphs. These are the first known PTASs for @math -hard optimization problems on disk graphs. They are based on a novel recursive subdivision of the plane that allows applying a shifting strategy on different levels simultaneously, so that a dynamic programming approach becomes feasible. The PTASs for disk graphs represent a common generalization of previous results for planar graphs and unit disk graphs. They can be extended to intersection graphs of other "disk-like" geometric objects (such as squares or regular polygons), also in higher dimensions. A unit disk graph is the intersection graph of unit disks in the euclidean plane. We present a polynomial-time approximation scheme for the maximum weight independent set problem in unit disk graphs. In contrast to previously known approximation schemes, our approach does not require a geometric representation (specifying the coordinates of the disk centers). The approximation algorithm presented is robust in the sense that it accepts any graph as input and either returns a (1+e)-approximate independent set or a certificate showing that the input graph is no unit disk graph. The algorithm can easily be extended to other families of intersection graphs of geometric objects. The intersection graph of a set of geometric objects is defined as a graph G = (S, E) in which there is an edge between two nodes si, sj ∈ S if si ∩ sj ≠ 0. The problem of computing a maximum independent set in the intersection graph of a set of objects is known to be NP-complete for most cases in two and higher dimensions. We present approximation algorithms for computing a maximum independent set of intersection graphs of convex objects in R2. Specifically, given (i) a set of n line segments in the plane with maximum independent set of size α, we present algorithms that find an independent set of size at least (α (2 log(2n α)))1 2 in time O(n3) and (α (2log(2n α)))1 4 in time O(n4 3 logcn), (ii) a set of n convex objects with maximum independent set of size α, we present an algorithm that finds an independent set of size at least (α (2log(2n α)))1 3 in time O(n3 + τ (S)), assuming that S can be preprocessed in time τ(S) to answer certain primitive operations on these convex sets, and (iii) a set of n rectangles with maximum independent set of size βn, for β≤ 1, we present an algorithm that computes an independent set of size Ω (β2n). All our algorithms use the notion of partial orders that exploit the geometric structure of the convex objects. We consider the problem of computing minimum geometric hitting sets in which, given a set of geometric objects and a set of points, the goal is to compute the smallest subset of points that hit all geometric objects. The problem is known to be strongly NP-hard even for simple geometric objects like unit disks in the plane. Therefore, unless P=NP, it is not possible to get Fully Polynomial Time Approximation Algorithms (FPTAS) for such problems. We give the first PTAS for this problem when the geometric objects are half-spaces in Re3 and when they are an r-admissible set regions in the plane (this includes pseudo-disks as they are 2-admissible). Quite surprisingly, our algorithm is a very simple local search algorithm which iterates over local improvements only. We consider the problem of computing minimum geometric hitting sets in which, given a set of geometric objects and a set of points, the goal is to compute the smallest subset of points that hit all geometric objects. The problem is known to be strongly NP-hard even for simple geometric objects like unit disks in the plane. Therefore, unless P = NP, it is not possible to get Fully Polynomial Time Approximation Algorithms (FPTAS) for such problems. We give the first PTAS for this problem when the geometric objects are half-spaces in ℝ3 and when they are an r-admissible set regions in the plane (this includes pseudo-disks as they are 2-admissible). Quite surprisingly, our algorithm is a very simple local-search algorithm which iterates over local improvements only. The MAXIMUM INDEPENDENT SET problem in d-box graphs, i.e., in the intersection graphs of axis-parallel rectangles in Rd, is a challenge open problem. For any fixed d ≥ 2 the problem is NP-hard and no approximation algorithm with ratio o(logd-1 n) is known. In some restricted cases, e.g., for d-boxes with bounded aspect ratio, a PTAS exists [17]. In this paper we prove APX-hardness (and hence non-existence of a PTAS, unless P = NP), of the MAXIMUM INDEPENDENT SET problem in d-box graphs for any fixed d ≥ 3. We state also first explicit lower bound 443 442 on efficient approximability in such case. Additionally, we provide a generic method how to prove APX-hardness for many NP-hard graph optimization problems in d-box graphs for any fixed d ≥ 3. In 2-dimensional case we give a generic approach to NP-hardness results for these problems in highly restricted intersection graphs of axis-parallel unit squares (alternatively, in unit disk graphs). Unit disk graphs are the intersection graphs of equal sized circles in the plane: they provide a graph-theoretic model for broadcast networks (cellular networks) and for some problems in computational geometry. We show that many standard graph theoretic problems remain NP-complete on unit disk graphs, including coloring, independent set, domination, independent domination, and connected domination; NP-completeness for the domination problem is shown to hold even for grid graphs, a subclass of unit disk graphs. In contrast, we give a polynomial time algorithm for finding cliques when the geometric representation (circles in the plane) is provided. Computing the maximum number of disjoint elements in a collection C of geometric objects is a classical problem in computational geometry with applications ranging from frequency assignment in cellular networks to map labeling in computational cartography. The problem is equivalent to finding the independence number, α(GC), of the intersection graph GC of C, obtained by connecting two elements of C with an edge if and only if their intersection is nonempty. This is known to be an NP-hard task even for systems of segments in the plane with at most two different slopes. The best known polynomial time approximation algorithm for systems of arbitrary segments is due to Agarwal and Mustafa, and returns in the worst case an n1 2+o(1)-approximation for α. Using extensions of the Lipton-Tarjan separator theorem, we improve this result and present, for every e > 0, a polynomial time algorithm for computing α(GC) with approximation ratio at most ne. In contrast, for general graphs, for any e > 0 it is NP-hard to approximate the independence number within a factor of n1−e. We also give a subexponential time exact algorithm for computing the independence number of intersection graphs of arcwise connected sets in the plane. In the Maximum Weight Independent Set of Rectangles (MWISR) problem we are given a set of n axis-parallel rectangles in the 2D-plane, and the goal is to select a maximum weight subset of pairwise non-overlapping rectangles. Due to many applications, e.g. in data mining, map labeling and admission control, the problem has received a lot of attention by various research communities. We present the first (1 + e)-approximation algorithm for the MWISR problem with quasipolynomial running time 2poly(log n e). In contrast, the best known polynomial time approximation algorithms for the problem achieve superconstant approximation ratios of O(log log n) (unweighted case) and O(log n log log n) (weighted case). Key to our results is a new geometric dynamic program which recursively subdivides the plane into polygons of bounded complexity. We provide the technical tools that are needed to analyze its performance. In particular, we present a method of partitioning the plane into small and simple areas such that the rectangles of an optimal solution are intersected in a very controlled manner. Together with a novel application of the weighted planar graph separator theorem due to [4] this allows us to upper bound our approximation ratio by 1 + e. Our dynamic program is very general and we believe that it will be useful for other settings. In particular, we show that, when parametrized properly, it provides a polynomial time (1 + e)-approximation for the special case of the MWISR problem when each rectangle is relatively large in at least one dimension. Key to this analysis is a method to tile the plane in order to approximately describe the topology of these rectangles in an optimal solution. This technique might be a useful insight to design better polynomial time approximation algorithms or even a PTAS for the MWISR problem. In particular, note that our results imply that the MWISR problem is not APX-hard, unless NP ⊆ DTIME(2polylog (n)). Unit disk graphs are the intersection graphs of unit diameter closed disks in the plane. This paper reduces SATISFIABILITY to the problem of recognizing unit disk graphs. Equivalently, it shows that determining if a graph has sphericity 2 or less, even if the graph is planar or is known to have sphericity at most 3, is NP-hard. We show how this reduction can be extended to 3 dimensions, thereby showing that unit sphere graph recognition, or determining if a graph has sphericity 3 or less, is also NP-hard. We conjecture that K-sphericity is NP-hard for all fixed K greater than 1. An EPTAS (efficient PTAS) is an approximation scheme where e does not appear in the exponent of n, i.e., the running time is f(e)nc. We use parameterized complexity to investigate the possibility of improving the known approximation schemes for certain geometric problems to EPTAS. Answering an open question of Alber and Fiala [2], we show that Maximum Independent Set is W[1]-complete for the intersection graphs of unit disks and axis-parallel unit squares in the plane. A standard consequence of this result is that the @math time PTAS of [11] for Maximum Independent Set on unit disk graphs cannot be improved to an EPTAS. Similar results are obtained for the problem of covering points with squares. We study a geometric version of the Red-Blue Set Cover problem originally proposed by (2000) 1: given a red point set, a blue point set, and a set of objects, we want to choose a subset of objects to cover all the blue points, while minimizing the number of red points covered. We prove that the problem is NP-hard even when the objects are unit squares in 2D, and we give the first polynomial-time approximation scheme (PTAS) for this case. The technique we use simplifies and unifies previous PTASs for the weighted geometric set cover problem and the unique maximum coverage problem for 2D unit squares. We consider the maximum independent set problem on sparse graphs with maximum degree d. The best known result for the problem is an SDP based O(d log log d log d) approximation due to Halperin. It is also known that no o(d log2 d) approximation exists assuming the Unique Games Conjecture. We show the following two results: (i) The natural LP formulation for the problem strengthened by O(log4(d)) levels of the mixed-hierarchy has an integrality gap of O(d log2 d), where O(·) ignores some log log d factors. However, our proof is non-constructive, in particular it uses an entropy based approach due to Shearer, and does not give a O(d log2 d) approximation algorithm with sub-exponential running time. (ii) We give an O(d log d) approximation based on polylog(d)-levels of the mixed hierarchy that runs in nO(1) exp(logO(1) d) time, improving upon Halperin's bound by a modest log log d factor. Our algorithm is based on combining Halperin's approach together with an idea used by Ajtai, Erdos, Komlos and Szemeredi to show that Kr-free, degree-d graphs have independent sets of size Ωr(n log log d d). In this paper, we study the following disc covering problem: Given a set of discs of various radii on the plane and centers on the grid points, find a subset of discs to maximize the area covered by exactly one disc. Thisproblem originates from the application in digital halftoning, with the best known approximation factor being 5.83 (, 2004). We show that if their radii are between two positive constants, then there exists a polynomial time approximation scheme. Our techniques are based on the width-bounded geometric separator recently developed in Fu and Wang (2004), Fu (2006). We consider the following packing problem. Let α be a fixed real in (0, 1]. We are given a bounding rectangle ρ and a set of n possibly intersecting unit disks whose centers lie in ρ. The task is to pack a set of m disjoint disks of radius α into ρ such that no disk in B intersects a disk in , where m is the maximum number of unit disks that can be packed. In this paper we present a polynomial-time algorithm for α = 2 3. So far only the case of packing squares has been considered. For that case, Baur and Fekete have given a polynomial-time algorithm for α = 2 3 and have shown that the problem cannot be solved in polynomial time for any α > 13 14 unless . 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. In the 0-extension problem, we are given a weighted graph with some nodes marked as terminals and a semimetric on the set of terminals. Our goal is to assign the rest of the nodes to terminals so as to minimize the sum, over all edges, of the product of the edge's weight and the distance between the terminals to which its endpoints are assigned. This problem generalizes the multiway cut problem of [SIAM J. Comput. , 23 (1994), pp. 864--894] and is closely related to the metric labeling problem introduced by Kleinberg and Tardos [Proceedings of the 40th IEEE Annual Symposium on Foundations of Computer Science, New York, 1999, pp. 14--23]. We present approximation algorithms for 0-Extension . In arbitrary graphs, we present a O(log k)-approximation algorithm, k being the number of terminals. We also give O(1)-approximation guarantees for weighted planar graphs. Our results are based on a natural metric relaxation of the problem previously considered by Karzanov [European J. Combin., 19 (1998), pp. 71--101]. It is similar in flavor to the linear programming relaxation of Garg, Vazirani, and Yannakakis [SIAM J. Comput. , 25 (1996), pp. 235--251] for the multicut problem, and similar to relaxations for other graph partitioning problems. We prove that the integrality ratio of the metric relaxation is at least @math for a positive c for infinitely many k. Our results improve some of the results of Kleinberg and Tardos, and they further our understanding on how to use metric relaxations. Let G be a planar graph with n vertices and with a partition of the vertex set into subsets V"0,...,V"k"-"1 for some positive integer [email protected][email protected]?n. Let S be a set of n distinct points in the plane with a partition into subsets S"0,...,S"k"-"1 with |V"i|=|S"i| ([email protected][email protected]?k-1). This paper studies the problem of computing a planar polyline drawing of G, such that each vertex of V"i is mapped to a distinct point of S"i. Lower and upper bounds on the number of bends per edge are proved for any [email protected][email protected]?n. In the special case k=n, we improve the upper and lower bounds presented in a paper by Pach and Wenger [J. Pach, R. Wenger, Embedding planar graphs at fixed vertex locations, Graphs and Combinatorics 17 (2001) 717-728]. The upper bound is based on an algorithm for computing a topological book embedding of a planar graph, such that the vertices follow a given left-to-right order and the number of crossings between every edge and the spine is asymptotically optimal, which can be regarded as a result of independent interest. We present 1 ? ?approximation algorithms for the maximum matching problem in location aware unit disc graphs and in growth-bounded graphs. The algorithm for unit disk graph is local in the sense that whether or not an edge is in the matching depends only on other vertices which are at most a constant number of hops away from it. The algorithm for growth-bounded graphs needs at most @math @math communication rounds during its execution. Using these matching algorithms we can compute vertex covers of the respective graph classes whose size are at most twice the optimal. The authors describe a general-purpose, representation-independent method for the accurate and computationally efficient registration of 3-D shapes including free-form curves and surfaces. The method handles the full six degrees of freedom and is based on the iterative closest point (ICP) algorithm, which requires only a procedure to find the closest point on a geometric entity to a given point. The ICP algorithm always converges monotonically to the nearest local minimum of a mean-square distance metric, and the rate of convergence is rapid during the first few iterations. Therefore, given an adequate set of initial rotations and translations for a particular class of objects with a certain level of 'shape complexity', one can globally minimize the mean-square distance metric over all six degrees of freedom by testing each initial registration. One important application of this method is to register sensed data from unfixtured rigid objects with an ideal geometric model, prior to shape inspection. Experimental results show the capabilities of the registration algorithm on point sets, curves, and surfaces. >