Let C be a compact set in R~2 and let S be a set of n points in R~2. We consider the problem of computing a translate of C that contains the maximum number, κ~*, of points of S. It is known that this problem can be solved in a time that is roughly quadratic in n. We show how random-sampling and bucketing techniques can be used to develop a near-linear-time Monte Carlo algorithm that computes a placement of C containing at least (1-ε)κ~* points of S, for given ε > 0, with high probability. We also present a deterministic algorithm that solves the ε-approximate version of the optimal-placement problem and runs in O(n~(1+δ) + n/ε) log m) time, for arbitrary constant δ > 0, if C is a convex m-gon.
展开▼
机译：让C成为R〜2中的紧凑型，让S在R〜2中成为一组N点。我们考虑计算包含最大数量，κ〜*的C的翻译问题。众所周知，在n大致二次的时间中可以解决这个问题。我们展示了随机采样和铲斗技术如何用于开发近线性时间蒙特卡罗算法，该近线性蒙特卡罗算法计算包含至少（1ε）κ〜*点的C的置位，因为给定ε> 0，概率很高。我们还提出了一种确定性算法，其解决了最佳放置问题的ε - 近似版本，并在O（n〜（1 +Δ）+ n /ε）log m）时间，对于任意常数Δ> 0，如果c是一个凸m-gon。
展开▼
