The maximum exposure problem
The maximum exposure problem
复制标题
最大曝光问题
DOI：
10.1016/j.comgeo.2022.101861
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Suri, Subhash
中科院分区：
文献类型：
--
作者：
Kumar, Neeraj;Sintos, Stavros;Suri, Subhash
给定平面上的一组点 P 和轴对齐的矩形 R，如果点 p∈ P 位于 R 中所有矩形之外，则该点称为暴露。在最大曝光问题中，给定整数参数 k，我们希望从 R 中删除 k 个矩形，以便最大化暴露点的数量。我们证明这个问题是 NP 困难的，并且即使 R 中的矩形是两个固定矩形的平移，假设合理的复杂性猜想也很难近似。然而，如果 R 仅由单个矩形的平移组成，我们提出多项式时间近似方案。对于一般矩形定义的范围空间，我们提出了一种简单的O(k)双标准逼近算法；也就是说，通过删除 O (k 2) 个矩形，我们可以暴露至少 Ω (1/k) 的最佳点数。
Given a set of points P and axis-aligned rectangles R in the plane, a point p∈ P is called exposed if it lies outside all rectangles in R. In the max-exposure problem, given an integer parameter k, we want to delete k rectangles from R 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 R are translates of two fixed rectangles. However, if R 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 Ω (1/k) of the optimal number of points.