非表示:
キーワード:
-
要旨:
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.
