de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

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.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-30AD-1
Zusammenfassung
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.