English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Translating a Planar Object to Maximize Point Containment

Agarwal, P., Hagerup, T., Ray, R., Sharir, M., Smid, M., & Welzl, E. (2002). Translating a Planar Object to Maximize Point Containment. In Algorithms - ESA 2002: 10th Annual European Symposium (pp. 42-53). Berlin, Germany: Springer.

Item is

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Agarwal, Pankaj, Author
Hagerup, Torben1, Author           
Ray, Rahul1, Author           
Sharir, Micha, Author
Smid, Michiel1, Author           
Welzl, Emo, Author
Möhring, Rolf, Editor
Raman, Rajeev1, Editor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: 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.

Details

show
hide
Language(s): eng - English
 Dates: 2003-09-082002
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 202060
Other: Local-ID: C1256428004B93B8-DEDAEE38A05F3663C1256C850055D604-Rahul2002
 Degree: -

Event

show
hide
Title: ESA 2002
Place of Event: Rome, Italy
Start-/End Date: 2002-09-17 - 2002-09-21

Legal Case

show

Project information

show

Source 1

show
hide
Title: Algorithms - ESA 2002 : 10th Annual European Symposium
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 42 - 53 Identifier: -

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 2461 Sequence Number: - Start / End Page: - Identifier: ISSN: 0302-9743