# Translating a planar object to maximize point containment

Conference Paper

bet C be a compact set in R and let S be a set of n points in R . 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 + n/ε)logm) time, for arbitrary constant δ> 0, if C is a convex m-gon. 2 2 1+δ

### Full Text

### 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

### Digital Object Identifier (DOI)

- 10.1007/3-540-45749-6_8

### Citation Source

- Scopus