Covering and packing of rectilinear subdivision

DOI10.1016/j.tcs.2020.07.038zbMath1455.68231arXiv1809.07214OpenAlexW4214929162MaRDI QIDQ5918965

Supantha Pandit, Satyabrata Jana

Publication date: 17 September 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1809.07214

zbMATH Keywords

independent setdominating setNP-hardnessPTASset coverplanar subdivision

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Approximation algorithms for maximum independent set of pseudo-disks
• Improved results on geometric hitting set problems
• Optimal packing and covering in the plane are NP-complete
• Guarding rectangular art galleries
• Line segment covering of cells in arrangements
• Approximation Algorithms for Independent Sets in Map Graphs
• Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
• Map graphs
• Covering, Hitting, Piercing and Packing Rectangles Intersecting an Inclined Line
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation schemes for covering and packing problems in image processing and VLSI
• Planar Formulae and Their Uses
• The Problem of Compatible Representatives
• Approximation algorithms for NP-complete problems on planar graphs
• Covering and packing of rectilinear subdivision