Covering many or few points with unit disks

DOI10.1007/S00224-008-9135-9MaRDI QIDQ839638zbMATH OpenOpenAlexFDO

Authors Mark de Berg, S. Cabello, Sariel Har-Peled

Publication date 2 September 2009

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-008-9135-9

zbMATH Keywords

facility locationgeometric optimizationweighted pointsrandom sample

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Recommendations

• Covering Many or Few Points with Unit Disks
• Unit disk cover problem in 2D
• Covering Points by Unit Disks of Fixed Location
• On the discrete unit disk cover problem
• On the discrete unit disk cover problem

Cites work

• scientific article; zbMATH DE number 1253058 (Why is no real title available?)
• scientific article; zbMATH DE number 1947380 (Why is no real title available?)
• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• An Expander-Based Approach to Geometric Optimization
• Applications of random sampling in computational geometry. II
• Approximation schemes for covering and packing problems in image processing and VLSI
• Approximations and optimal geometric divide-and-conquer
• Covering point sets with two disjoint disks or squares
• Efficient partition trees
• Exact and approximation algorithms for clustering
• Improved algorithms for placing undesirable facilities
• Note—On a Modified One-Center Model
• On Approximating the Depth and Related Problems
• On \(k\)-sets in arrangements of curves and surfaces
• On a circle placement problem
• On a class of \(O(n^ 2)\) problems in computational geometry
• Translating a regular grid over a point set

Cited in

(22)

• How many intervals cover a point in Dvoretzky covering?
• The most points connected-covering problem with two disks
• An improved approximation algorithm for the most points covering problem
• Covering polygons with rectangles
• Assigning weights to minimize the covering radius in the plane
• Faster algorithms for some optimization problems on collinear points
• Near-linear time approximation schemes for geometric maximum coverage
• Output sensitive algorithm for covering many points
• A novel approximation algorithm for max-covering circle problem
• The line-constrained maximum coverage facility location problem
• Placing two axis-parallel squares to maximize the number of enclosed points
• On isolating points using unit disks
• New exact algorithms for planar maximum covering location by ellipses problems
• Minimum-cost coverage of point sets by disks
• Linear Time Approximation Schemes for Geometric Maximum Coverage
• Fuzzy disk for covering fuzzy points
• On Isolating Points Using Disks
• Covering Many or Few Points with Unit Disks
• Approximation algorithms for finding maximum containing circle and sphere
• A PTAS for the cardinality constrained covering with unit balls
• Experiments with unit disk cover algorithms for covering massive pointsets
• Enclosing weighted points with an almost-unit ball

This page was built for publication: Covering many or few points with unit disks

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