# Translating a planar object to maximize point containment

Published

Conference Paper

© Springer-Verlag Berlin Heidelberg 2002. bet 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, K*, of pointsof 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 — ε)K* 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/ε)logm) time, for arbitrary constant δ> 0, if C is a convex m-gon.

### Duke Authors

### Cited Authors

- Agarwal, PK; Hagerup, T; Ray, R; Sharir, M; Smid, M; Welzl, E

### Published Date

- January 1, 2002

### Published In

### Volume / Issue

- 2461 /

### Start / End Page

- 42 - 53

### Electronic International Standard Serial Number (EISSN)

- 1611-3349

### International Standard Serial Number (ISSN)

- 0302-9743

### International Standard Book Number 10 (ISBN-10)

- 3540441808

### International Standard Book Number 13 (ISBN-13)

- 9783540441809

### Citation Source

- Scopus