Translating a planar object to maximize point containment

Conference Paper

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

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