The maximum exposure problem

DOI10.1016/J.COMGEO.2022.101861zbMATH Open1483.68466arXiv2102.03455OpenAlexW4210371740MaRDI QIDQ2123293FDOQ2123293

Neeraj Kumar, Subhash Suri, Stavros Sintos

Publication date: 8 April 2022

Published in: Computational Geometry (Search for Journal in Brave)

Abstract: Given a set of points $P$ and axis-aligned rectangles $mathcalR$ in the plane, a point $pinP$ is called emph{exposed} if it lies outside all rectangles in $mathcalR$. In the emph{max-exposure problem}, given an integer parameter $k$, we want to delete $k$ rectangles from $mathcalR$ so as to maximize the number of exposed points. We show that the problem is NP-hard and assuming plausible complexity conjectures is also hard to approximate even when rectangles in $mathcalR$ are translates of two fixed rectangles. However, if $mathcalR$ only consists of translates of a single rectangle, we present a polynomial-time approximation scheme. For range space defined by general rectangles, we present a simple $O(k)$ bicriteria approximation algorithm; that is by deleting $O(k^2)$ rectangles, we can expose at least $Omega(1/k)$ of the optimal number of points.

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

Recommendations

• Covering points by disjoint boxes with outliers
• Linear Time Approximation Schemes for Geometric Maximum Coverage
• Maximum independent set of rectangles
• The class cover problem with boxes
• Covering many points with a small-area box

zbMATH Keywords

network resiliencePTASdensest k-subgraphgeometric constraint removalmax-exposure

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cites Work

• A threshold of ln n for approximating set cover
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• Applications of random sampling in computational geometry. II
• Almost optimal set covers in finite VC-dimension
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
• Greedily Finding a Dense Subgraph
• The dense \(k\)-subgraph problem
• Approximation schemes for covering and packing problems in image processing and VLSI
• Optimal packing and covering in the plane are NP-complete
• The Densest $k$-Subhypergraph Problem
• On the complexity of barrier resilience for fat regions and bounded ply
• On the set multicover problem in geometric settings
• Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion
• Approximation algorithms for union and intersection covering problems
• Title not available (Why is that?)
• The Maximum Exposure Problem.

Cited In (1)

• On the parameterized complexity of the Maximum Exposure Problem

This page was built for publication: The maximum exposure problem

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