Experiments with unit disk cover algorithms for covering massive pointsets

DOI10.1016/J.COMGEO.2022.101925MaRDI QIDQ2096372zbMATH OpenOpenAlexWikidataFDO

Authors Yanyan Li

Publication date 16 November 2022

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2205.01716

zbMATH Keywords

experimentsgeometric coveringunit disk

Mathematics Subject Classification ID

Theory of computing (68Qxx) Computing methodologies and applications (68Uxx) Algorithms in computer science (68Wxx)

Recommendations

• On the discrete unit disk cover problem
• On the discrete unit disk cover problem
• Approximation algorithms for the unit disk cover problem in 2D and 3D
• Unit disk cover problem in 2D
• Practical Discrete Unit Disk Cover Using an Exact Line-Separable Algorithm

Cites work

• A note on multicovering with disks
• Almost optimal set covers in finite VC-dimension
• An Almost Linear Time 2.8334-Approximation Algorithm for the Disc Covering Problem
• Approximation algorithms for the unit disk cover problem in 2D and 3D
• Approximation schemes for covering and packing problems in image processing and VLSI
• Covering a set of points in multidimensional space
• Covering many or few points with unit disks
• Incremental Clustering and Dynamic Information Retrieval
• Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
• On a circle placement problem
• On the discrete unit disk cover problem
• Optimal cover of points by disks in a simple polygon
• Optimal packing and covering in the plane are NP-complete
• Polynomial time approximation schemes for minimum disk cover problems
• Practical and efficient algorithms for the geometric hitting set problem

Cited in

(5)

• UnitDiskCoverAlgorithms
• Covering a set of points with a minimum number of equal disks via simulated annealing
• Online hitting of unit balls and hypercubes in \(\mathbb{R}^d\) using points from \(\mathbb{Z}^d\)
• Bounded-degree plane geometric spanners in practice
• Engineering an algorithm for constructing low-stretch geometric graphs with near-greedy average degrees

Describes a project that uses

Uses Software

• CGAL

This page was built for publication: Experiments with unit disk cover algorithms for covering massive pointsets

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