Packing and covering with non-piercing regions
From MaRDI portal
Publication:1991095
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Combinatorial optimization (90C27)
Recommendations
- Packing and covering with non-piercing regions
- Local search strikes again: PTAS for variants of geometric covering and packing
- Local search strikes again: PTAS for variants of geometric covering and packing
- Geometric Packing under Nonuniform Constraints
- Geometric packing under non-uniform constraints
Cites work
- A QPTAS for maximum weight independent set of polygons with polylogarithmically many vertices
- A Separator Theorem for Planar Graphs
- Algorithms for dominating set in disk graphs: breaking the \(\log n\) barrier (extended abstract)
- Almost optimal set covers in finite VC-dimension
- Approximation algorithms for maximum independent set of pseudo-disks
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- Approximation Schemes for Covering and Packing
- Effectiveness of local search for geometric optimization
- Fast approximation algorithms for a nonconvex covering problem
- Geometric packing under non-uniform constraints
- Guarding terrains via local search
- Hitting sets when the VC-dimension is small
- scientific article; zbMATH DE number 5764844 (Why is no real title available?)
- scientific article; zbMATH DE number 1749054 (Why is no real title available?)
- Improved results on geometric hitting set problems
- Independent set of intersection graphs of convex objects in 2D
- Label placement by maximum independent set in rectangles
- Minimum vertex cover in rectangle graphs
- New existence proofs ε-nets
- Polynomial-time approximation schemes for packing and piercing fat objects
- Quasi-polynomial time approximation scheme for sparse subsets of polygons
- Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
- Separating a Voronoi diagram via local search
- Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
- Weighted geometric set cover via quasi-uniform sampling
Cited in
(19)- Maintenance of a piercing set for intervals with applications
- A primal-dual algorithm for the minimum power partial cover problem
- On the geometric set multicover problem
- Constructing planar support for non-piercing regions
- Minimum power partial multi-cover on a line
- Geometric packing under non-uniform constraints
- scientific article; zbMATH DE number 124521 (Why is no real title available?)
- scientific article; zbMATH DE number 1182895 (Why is no real title available?)
- Packing and covering with non-piercing regions
- Planar Support for Non-piercing Regions and Applications
- scientific article; zbMATH DE number 3342063 (Why is no real title available?)
- On the geometric priority set cover problem
- Geometric stabbing via threshold rounding and factor revealing LPs
- Sweeping arrangements of non-piercing regions in the plane
- Geometric covering via extraction theorem
- On hypergraph supports (extended abstract)
- A fast algorithm for computing a planar support for non-piercing rectangles
- Covering simple orthogonal polygons with rectangles
- On supports for graphs of bounded genus
This page was built for publication: Packing and covering with non-piercing regions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1991095)
