Translating a planar object to maximize point containment

Published

Conference Paper

© Springer-Verlag Berlin Heidelberg 2002. 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.

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