Item

Abstract

Let $C$ be a compact set in $\IR^2$ and let $S$ be a set of $n$ points in $\IR^2$. We consider the problem of computing a translate of $C$ that contains the maximum number, $\kappa^*$, of points %denoted by $\kappa^*$, 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-\eps) \kappa^*$ points of $S$, for given $\eps>0$, with high probability. Finally, we present a deterministic algorithm that solves the $\eps$-approximate version of the optimal-placement problem for convex $m$-gons in $O(n^{1+\delta} + (n/\eps)\log m)$ time, for arbitrary constant $\delta>0$. %, for convex $m$-gons.