Output sensitive algorithm for covering many points

MaRDI QIDQ5249243zbMATH OpenFDO

Authors Hossein Ghasemalizadeh, Mohammadreza Razzazi

Publication date 30 April 2015

Full work available at URL https://arxiv.org/abs/1312.0389, https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2303/0.html

zbMATH Keywords

computational geometryoutput-sensitive algorithmcovering with disks

Mathematics Subject Classification ID

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

Recommendations

• An improved approximation algorithm for the most points covering problem
• An Almost Linear Time 2.8334-Approximation Algorithm for the Disc Covering Problem
• Covering Many or Few Points with Unit Disks
• Covering many or few points with unit disks
• Unit disk cover problem in 2D

Cited in

(2)

• Output sensitive algorithms for approximate incidences and their applications
• The most points connected-covering problem with two disks

This page was built for publication: Output sensitive algorithm for covering many points

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