Discrete unit square cover problem

DOI10.1142/S1793830918500726zbMath1412.68294OpenAlexW2890438734WikidataQ129329692 ScholiaQ129329692MaRDI QIDQ4644781

Manjanna Basappa, Gautam K. Das

Publication date: 9 January 2019

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s1793830918500726

zbMATH Keywords

approximation algorithmssweep-line algorithmdiscrete unit square cover

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items (1)

Minimum ply covering of points with unit squares

Cites Work

• Unit disk cover problem in 2D
• The within-strip discrete unit disk cover problem
• Improved results on geometric hitting set problems
• Covering a set of points in a plane using two parallel rectangles
• Homogeneous 2-hop broadcast in 2D
• Optimal packing and covering in the plane are NP-complete
• Almost optimal set covers in finite VC-dimension
• Geometric red-blue set cover for unit squares and related problems
• A Polynomial-Time Approximation Scheme for the Geometric Unique Coverage Problem on Unit Squares
• AN IMPROVED LINE-SEPARABLE ALGORITHM FOR DISCRETE UNIT DISK COVER
• PTAS for Weighted Set Cover on Unit Squares
• Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
• Approximation schemes for covering and packing problems in image processing and VLSI
• ON THE DISCRETE UNIT DISK COVER PROBLEM
• Covering Points by Unit Disks of Fixed Location
• Line segment disk cover
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Discrete unit square cover problem