Algorithms for the line-constrained disk coverage and related problems

DOI10.1007/978-3-030-83508-8_42OpenAlexW3197259003MaRDI QIDQ5896893

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

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• Some variations on constrained minimum enclosing circle problem
• Polynomial time approximation schemes for base station coverage with minimum total radii
• WEIGHTED GEOMETRIC SET COVER PROBLEMS REVISITED
• Line-Constrained k-Median, k-Means, and k-Center Problems in the Plane
• Algorithms for Reporting and Counting Geometric Intersections
• A threshold of ln n for approximating set cover
• A PTAS for the Weighted Unit Disk Cover Problem
• AN IMPROVED LINE-SEPARABLE ALGORITHM FOR DISCRETE UNIT DISK COVER
• Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
• Practical Discrete Unit Disk Cover Using an Exact Line-Separable Algorithm
• Fast approximation algorithms for a nonconvex covering problem
• Comments on “algorithms for reporting and counting geometric intersections”
• On the hardness of approximating minimization problems
• PTAS for geometric hitting set problems via local search
• Algorithms – ESA 2005

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