de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

#### Translating a Planar Object to Maximize Point Containment

##### MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44564

Hagerup,  Torben
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45268

Ray,  Rahul
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45509

Smid,  Michiel
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45250

Raman,  Rajeev
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
##### Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
##### Zitation

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.

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.