Near-linear time approximation schemes for geometric maximum coverage

DOI10.1016/J.TCS.2017.11.026zbMATH Open1391.68111arXiv1702.01836OpenAlexW4243044215MaRDI QIDQ1748995FDOQ1748995

Authors: Kai Jin, Jian Li, Haitao Wang, Bowei Zhang, N. Zhang 

Publication date: 15 May 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: We study approximation algorithms for the following geometric version of the maximum coverage problem: Let $mathcalP$ be a set of $n$ weighted points in the plane. Let $D$ represent a planar object, such as a rectangle, or a disk. We want to place $m$ copies of $D$ such that the sum of the weights of the points in $mathcalP$ covered by these copies is maximized. For any fixed $varepsilon>0$, we present efficient approximation schemes that can find a $(1-varepsilon)$-approximation to the optimal solution. In particular, for $m=1$ and for the special case where $D$ is a rectangle, our algorithm runs in time $O(nlog(frac1varepsilon))$, improving on the previous result. For $m>1$ and the rectangular case, our algorithm runs in $O(fracnvarepsilonlog(frac1varepsilon)+fracmvarepsilonlogm+m(frac1varepsilon{)}^{O(min(sqrtm,frac1varepsilon))})$ time. For a more general class of shapes (including disks, polygons with $O(1)$ edges), our algorithm runs in $O(n(frac1varepsilon{)}^{O(1)}+fracmepsilonlogm+m(frac1varepsilon{)}^{O(min(m,frac1varepsilo{n}^2))})$ time.

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

Recommendations

• Linear Time Approximation Schemes for Geometric Maximum Coverage
• Improved approximation algorithms for geometric set cover
• Improved approximation algorithms for geometric set cover
• Covering Many or Few Points with Unit Disks
• Covering many or few points with unit disks

zbMATH Keywords

polynomial-time approximation schemegeometric set covermaximum coverage

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Discrete location and assignment (90B80)

Cites Work

• A threshold of ln n for approximating set cover
• Introduction to algorithms.
• A Reliable Randomized Algorithm for the Closest-Pair Problem
• An efficient algorithm for determining the convex hull of a finite planar set
• Hitting sets when the VC-dimension is small
• Optimal placement of convex polygons to maximize point containment
• Almost optimal set covers in finite VC-dimension
• Weighted geometric set cover via quasi-uniform sampling
• Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
• Covering point sets with two disjoint disks or squares
• An analysis of approximations for maximizing submodular set functions—I
• Exact and approximation algorithms for clustering
• On the Complexity of Some Common Geometric Location Problems
• Approximation schemes for covering and packing problems in image processing and VLSI
• Note—On a Modified One-Center Model
• Geometric approximation algorithms
• Faster all-pairs shortest paths via circuit complexity
• Approximation of convex bodies by rectangles
• Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
• Improved approximation algorithms for geometric set cover
• Necklaces, Convolutions, and X + Y
• Title not available (Why is that?)
• On Approximating the Depth and Related Problems
• Title not available (Why is that?)
• Approximations and optimal geometric divide-and-conquer
• PTAS for geometric hitting set problems via local search
• Title not available (Why is that?)
• A PTAS for the Weighted Unit Disk Cover Problem
• On a circle placement problem
• Covering many or few points with unit disks
• A unified algorithm for finding maximum and minimum object enclosing rectangles and cuboids
• Translating a convex polygon to contain a maximum number of points.

Cited In (8)

• Title not available (Why is that?)
• An algorithmic framework for solving geometric covering problems -- with applications
• Title not available (Why is that?)
• Energy-constrained geometric coverage problem
• A Polynomial-Time Approximation Scheme for the Geometric Unique Coverage Problem on Unit Squares
• Tight Bounds for Beacon-Based Coverage in Simple Rectilinear Polygons
• Linear Time Approximation Schemes for Geometric Maximum Coverage
• Approximation algorithms for finding maximum containing circle and sphere

This page was built for publication: Near-linear time approximation schemes for geometric maximum coverage

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