A 4.31-approximation for the geometric unique coverage problem on unit disks

DOI10.1007/978-3-642-35261-4_40MaRDI QIDQ4909554zbMATHOpenAlexFDO

Authors Takehiro Ito, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Yushi Uno, Shin-Ichi Nakano

Publication date 21 March 2013

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-35261-4_40

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• A 4.31-approximation for the geometric unique coverage problem on unit disks
• A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares
• A Polynomial-Time Approximation Scheme for the Geometric Unique Coverage Problem on Unit Squares
• Covering Points by Unit Disks of Fixed Location
• Unit disk cover problem in 2D

Cited in

(6)

• Combination Can Be Hard: Approximability of the Unique Coverage Problem
• A Polynomial-Time Approximation Scheme for the Geometric Unique Coverage Problem on Unit Squares
• A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares
• A 4.31-approximation for the geometric unique coverage problem on unit disks
• Minimum membership covering and hitting
• Unique coverage with rectangular regions

This page was built for publication: A 4.31-approximation for the geometric unique coverage problem on unit disks

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