Algorithms for the line-constrained disk coverage and related problems

DOI10.1007/978-3-030-83508-8_42MaRDI QIDQ5896893zbMATH OpenOpenAlexFDO

Authors Logan Pedersen, Haitao Wang

Publication date 25 March 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

facility locationdisk coveragegeometric coveragehalf-plane coverageline-constrained

Mathematics Subject Classification ID

Data structures (68P05) Algorithms in computer science (68Wxx)

Recommendations

• Algorithms for the line-constrained disk coverage and related problems
• Practical Discrete Unit Disk Cover Using an Exact Line-Separable Algorithm
• An improved line-separable algorithm for discrete unit disk cover
• The coverage problem by aligned disks
• The Coverage Problem by Aligned Disks
• Approximation algorithms for the unit disk cover problem in 2D and 3D
• An Almost Linear Time 2.8334-Approximation Algorithm for the Disc Covering Problem
• The bound coverage problem by aligned disks in \(L_1\) metric
• On the discrete unit disk cover problem
• On the discrete unit disk cover problem

Cites work

• A PTAS for the Weighted Unit Disk Cover Problem
• A threshold of ln n for approximating set cover
• Algorithms for Reporting and Counting Geometric Intersections
• Algorithms – ESA 2005
• An improved line-separable algorithm for discrete unit disk cover
• Comments on “algorithms for reporting and counting geometric intersections”
• Computational geometry. Algorithms and applications.
• Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• Fast approximation algorithms for a nonconvex covering problem
• Faster algorithms for some optimization problems on collinear points
• Line-Constrained k-Median, k-Means, and k-Center Problems in the Plane
• Minimum-cost coverage of point sets by disks
• On the hardness of approximating minimization problems
• PTAS for geometric hitting set problems via local search
• Polynomial time approximation schemes for base station coverage with minimum total radii
• Practical Discrete Unit Disk Cover Using an Exact Line-Separable Algorithm
• Some variations on constrained minimum enclosing circle problem
• Weighted geometric set cover problems revisited

Cited in

(6)

• Algorithms for the line-constrained disk coverage and related problems
• A note on minimum-sum coverage by aligned disks
• An Almost Linear Time 2.8334-Approximation Algorithm for the Disc Covering Problem
• Practical Discrete Unit Disk Cover Using an Exact Line-Separable Algorithm
• An optimal algorithm for the minimum disc cover problem
• The within-strip discrete unit disk cover problem

This page was built for publication: Algorithms for the line-constrained disk coverage and related problems

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