An algorithmic framework for solving geometric covering problems -- with applications
DOI10.1142/S0129054114500257zbMATH Open1302.68287MaRDI QIDQ2929639FDOQ2929639
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)
Recommendations
approximation algorithmcomputational geometrygeometric coveringset cover problemalgorithmic frameworkcovering with diskscovering with obstaclescovering with sectors
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)
Cites Work
- A threshold of ln n for approximating set cover
- Generalized submodular cover problems and applications
- An analysis of the greedy algorithm for the submodular set covering problem
- Almost optimal set covers in finite VC-dimension
- An improved line-separable algorithm for discrete unit disk cover
- Approximation algorithms for partial covering problems
- Improved results on geometric hitting set problems
- Exact and approximation algorithms for clustering
- Approximation schemes for covering and packing problems in image processing and VLSI
- Fast algorithms for computing the smallest \(k\)-enclosing circle
- Improved approximation algorithms for geometric set cover
- Covering a set of points in multidimensional space
- A Tight Analysis of the Greedy Algorithm for Set Cover
- The multi-facility location-allocation problem with polyhedral barriers
- The 2-center problem with obstacles
- Covering Problems with Hard Capacities
- On a circle placement problem
- An improved approximation algorithm for the most points covering problem
Cited In (8)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A PTAS for a disc covering problem using width-bounded separators
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
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)
