Covering many or few points with unit disks

DOI10.1007/S00224-008-9135-9zbMATH Open1187.68716OpenAlexW2934288247MaRDI QIDQ839638FDOQ839638

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

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

zbMATH Keywords

facility locationgeometric optimizationweighted pointsrandom sample

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Cites Work

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

Cited In (22)

• The most points connected-covering problem with two disks
• How many intervals cover a point in Dvoretzky covering?
• An improved approximation algorithm for the most points covering problem
• Assigning weights to minimize the covering radius in the plane
• Covering polygons with rectangles
• 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)