An algorithmic framework for solving geometric covering problems -- with applications

DOI10.1142/S0129054114500257MaRDI QIDQ2929639zbMATH OpenFDO

Authors Taha Ghasemi, Hossein Ghasemalizadeh, Mohammadreza Razzazi

Publication date 14 November 2014

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmcomputational geometrygeometric coveringset cover problemalgorithmic frameworkcovering with diskscovering with obstaclescovering with sectors

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15)

Recommendations

• Approximation Schemes for Covering and Packing
• A PTAS for the disk cover problem of geometric objects
• Improved approximation algorithms for geometric set cover
• Improved approximation algorithms for geometric set cover
• Near-linear time approximation schemes for geometric maximum coverage

Cites work

• A Tight Analysis of the Greedy Algorithm for Set Cover
• A threshold of ln n for approximating set cover
• Almost optimal set covers in finite VC-dimension
• An analysis of the greedy algorithm for the submodular set covering problem
• An improved approximation algorithm for the most points covering problem
• An improved line-separable algorithm for discrete unit disk cover
• Approximation algorithms for partial covering problems
• Approximation schemes for covering and packing problems in image processing and VLSI
• Covering Problems with Hard Capacities
• Covering a set of points in multidimensional space
• Exact and approximation algorithms for clustering
• Fast algorithms for computing the smallest \(k\)-enclosing circle
• Generalized submodular cover problems and applications
• Improved approximation algorithms for geometric set cover
• Improved results on geometric hitting set problems
• On a circle placement problem
• The 2-center problem with obstacles
• The multi-facility location-allocation problem with polyhedral barriers

Cited in

(8)

• scientific article; zbMATH DE number 7378687 (Why is no real title available?)
• scientific article; zbMATH DE number 7376034 (Why is no real title available?)
• A PTAS for a disc covering problem using width-bounded separators
• scientific article; zbMATH DE number 2000148 (Why is no real title available?)
• Algorithms for the construction of an optimal cover for sets in three-dimensional Euclidean space
• Parameterized complexity of geometric covering problems having conflicts
• A PTAS for the disk cover problem of geometric objects
• scientific article; zbMATH DE number 1057736 (Why is no real title available?)

This page was built for publication: An algorithmic framework for solving geometric covering problems -- with applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2929639)