Optimal packing and covering in the plane are NP-complete
From MaRDI portal
Publication:1157170
DOI10.1016/0020-0190(81)90111-3zbMath0469.68053OpenAlexW2013451793WikidataQ57568241 ScholiaQ57568241MaRDI QIDQ1157170
Robert J. Fowler, Steven L. Tanimoto, Michael S. Paterson
Publication date: 1981
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(81)90111-3
Analysis of algorithms and problem complexity (68Q25) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Discrete mathematics in relation to computer science (68R99)
Related Items
Approximating Minimum-Area Rectangular and Convex Containers for Packing Convex Polygons, ON THE DISCRETE UNIT DISK COVER PROBLEM, Unnamed Item, On the complexity of some geometric problems in unbounded dimension, Boxicity and treewidth, A POLYNOMIAL-TIME APPROXIMATION ALGORITHM FOR A GEOMETRIC DISPERSION PROBLEM, Co-Clustering Under the Maximum Norm, ON PARAMETERIZED COMPLEXITY OF HITTING SET PROBLEM FOR AXIS–PARALLEL SQUARES INSTERSECTING A STRAIGHT LINE, Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph, Tiling with Squares and Packing Dominos in Polynomial Time, Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs, PACKING A TRUCK — NOW WITH A TWIST!, Mixed-Integer programming models for irregular strip packing based on vertical slices and feasibility cuts, Improving emergency services efficiency during Islamic pilgrimage through optimal allocation of facilities, Covering a set of points with a minimum number of equal disks via simulated annealing, On the geometric priority set cover problem, Exact algorithms and hardness results for geometric red-blue hitting set problem, Approximating the discrete center line segment in linear time, Unnamed Item, Hitting geometric objects online via points in \(\mathbb{Z}^d\), On Covering Problems of Rado, Online hitting of unit balls and hypercubes in \(\mathbb{R}^d\) using points from \(\mathbb{Z}^d\), Constrained hitting set problem with intervals: hardness, FPT and approximation algorithms, Constrained hitting set problem with intervals, Many disjoint edges in topological graphs, Covering Polygons with Rectangles, THE ALIGNED K-CENTER PROBLEM, Efficient Approximations for the Online Dispersion Problem, The Maximum Exposure Problem., Jump Number of Two-Directional Orthogonal Ray Graphs, AN IMPROVED LINE-SEPARABLE ALGORITHM FOR DISCRETE UNIT DISK COVER, Discrete unit square cover problem, Many disjoint edges in topological graphs, Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams., AN APPROXIMATION ALGORITHM FOR LOCATING MAXIMAL DISKS WITHIN CONVEX POLYGONS, Hierarchically specified unit disk graphs, Hitting and Piercing Rectangles Induced by a Point Set, Approximation algorithms for maximum two-dimensional pattern matching, On point covers of \(c-\)oriented polygons, Piercing all translates of a set of axis-parallel rectangles, TERRAIN DECOMPOSITION AND LAYERED MANUFACTURING, Cubicity of interval graphs and the claw number, Convex Cardinal Shape Composition, Computing coverage kernels under restricted settings, Disjoint edges in complete topological graphs, The pallet loading problem: a review of solution methods and computational experiments, Minimum membership covering and hitting, Combining Traditional Map Labeling with Boundary Labeling, A constant-factor approximation algorithm for red-blue set cover with unit disks, Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack, Unnamed Item, On Geometric Set Cover for Orthants, On the Discrete Unit Disk Cover Problem, Covering and packing of rectilinear subdivision, A constant-factor approximation algorithm for red-blue set cover with unit disks, Online unit covering in Euclidean space, Local search strikes again: PTAS for variants of geometric covering and packing, Coloring and Maximum Independent Set of Rectangles, Covering a set of line segments with a few squares, Covering a set of line segments with a few squares, ON PLANAR MEDIANOID COMPETITIVE LOCATION PROBLEMS WITH MANHATTAN DISTANCE, Dynamic data structures for fat objects and their applications, Locating two obnoxious facilities using the weighted maximin criterion, On capacitated covering with unit balls, Decision Trees for Geometric Models, Diameter partitioning, The maximum exposure problem, A mixed integer formulation for maximal covering by inclined parallelograms, Improved algorithms for resource allocation under varying capacity, \(\mathsf{NP}\)-hardness of geometric set cover and hitting set with rectangles containing a common point, Approximability and hardness of geometric hitting set with axis-parallel rectangles, Weighted geometric set cover with rectangles of bounded integer side lengths, Online unit clustering and unit covering in higher dimensions, A randomized algorithm for online unit clustering, On the complexity of some basic problems in computational convexity. I. Containment problems, Optimal packing of similar triangles, A mixed breadth-depth first strategy for the branch and bound tree of Euclidean \(k\)-center problems, A heuristic for the p-center problem in graphs, A simulated annealing approach to the nesting problem in the textile manufacturing industry, The nesting problem in the leather manufacturing industry, Target coverage with minimum number of camera sensors, Geometric optimization and the polynomial hierarchy, Parallel algorithm for minimum partial dominating set in unit disk graph, Packing 16, 17 or 18 circles in an equilateral triangle, Geometric optimization and \(D^ P\)-completeness, A new approach to cooperative competition in facility location problems: mathematical formulations and an approximation algorithm, A clique covering MIP model for the irregular strip packing problem, Max point-tolerance graphs, Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve, Complexity of tiling a polygon with trominoes or bars, Covering points by disjoint boxes with outliers, Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane, Optimal packings of 2,3, and 4 equal balls into a cubical flat 3-torus, Convexity in partial cubes: the hull number, Approximation algorithms for free-label maximization, Covering moving points with anchored disks, Near-linear approximation algorithms for geometric hitting sets, Theory and application of width bounded geometric separators, Piercing translates and homothets of a convex body, Lexicographic local search and the \(p\)-center problem., Dispersing points on intervals, A PTAS for the cardinality constrained covering with unit balls, Algorithmic aspects of proportional symbol maps, Hardness of approximation for non-overlapping local alignments., \(k\)-balanced center location problem: a new multi-objective facility location problem, Approximation algorithms for intersection graphs, Two approaches for heat transfer simulation of current carrying multicables, Rectangle blanket problem: binary integer linear programming formulation and solution algorithms, On the geometric red-blue set cover problem, Covering a set of points in multidimensional space, Co-clustering under the maximum norm, Unit disk cover problem in 2D, Independent set of convex polygons: from \(n^{\epsilon}\) to \(1+\epsilon \) via shrinking, Approximation algorithms for the unit disk cover problem in 2D and 3D, A streaming algorithm for 2-center with outliers in high dimensions, Matching colored points with rectangles, An algorithmic framework for labeling network maps, Packing problems, Numerical optimization method for packing regular convex polygons, Mixed integer quadratically-constrained programming model to solve the irregular strip packing problem with continuous rotations, The within-strip discrete unit disk cover problem, An improved approximation algorithm for the most points covering problem, Covering a polygonal region by rectangles, A unified model and algorithms for temporal map labeling, On covering problems of Rado, Minimum vertex cover in rectangle graphs, Orthogonal segment stabbing, Smooth kinetic maintenance of clusters, Hyperbolic set covering problems with competing ground-set elements, A clustering-based approach to kinetic closest pair, An exact algorithm for a class of geometric set-cover problems, Independent sets and hitting sets of bicolored rectangular families, Path optimization with limited sensing ability, The cubicity of hypercube graphs, Maximizing the number of obnoxious facilities to locate within a bounded region, Near-linear algorithms for geometric hitting sets and set covers, Translational packing of arbitrary polytopes, Selecting and covering colored points, Minimal sensor integrity: Measuring the vulnerability of sensor grids, On genetic algorithms for the packing of polygons, Hierarchically specified unit disk graphs, Fast optimal and bounded suboptimal Euclidean pathfinding, An upper bound for cubicity in terms of boxicity, Raster penetration map applied to the irregular packing problem, A simple heuristic for the p-centre problem, Label placement by maximum independent set in rectangles, A note on maximum independent sets in rectangle intersection graphs, Maximizing the ratio of cluster split to cluster diameter without and with cardinality constraints, Exact multi-covering problems with geometric sets, The most points connected-covering problem with two disks, An improved algorithm for online unit clustering, On the cubicity of certain graphs, On interval and circular-arc covering problems, On the complexity of locating linear facilities in the plane, Computing closely matching upper and lower bounds on textile nesting problems, Fast stabbing of boxes in high dimensions, Experiments with unit disk cover algorithms for covering massive pointsets, Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity, Lower bounds for boxicity, Combinatorial analysis (nonnegative matrices, algorithmic problems), Interval graphs and related topics, Location problems, Lattice coverage of cuboid with minimum number of hemispheres, On the complexity of two circle connecting problems, Piercing all translates of a set of axis-parallel rectangles
Cites Work
