MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Agarwal, Pankaj
Hagerup, Torben
Ray, Rahul
Sharir, Micha
Smid, Michiel
Welzl, Emo		dblp
dblp
dblp
dblp
dblp
dblp
Not MPG Author(s):
Agarwal, Pankaj
Hagerup, Torben
Sharir, Micha
Smid, Michiel
Welzl, Emo
Editor(s):
Möhring, Rolf
Raman, Rajeev		dblp
dblp
Not MPII Editor(s):
Möhring, Rolf
Raman, Rajeev
BibTeX cite key*:
Rahul2002b
Title, Booktitle
Title*:
Translating a Planar Object to Maximize Point Containment
Booktitle*:
Algorithms - ESA 2002 : 10th Annual European Symposium
Event, URLs
Conference URL::
http://www.dis.uniroma1.it/~algo02/esa02/
Downloading URL:
http://www.mpi-sb.mpg.de/~rahul/esa.ps
Event Address*:
Rome, Italy
Language:
English
Event Date*
(no longer used):
-- September 17 - 21, 2002
Organization:
EATCS
Event Start Date:
17 September 2002
Event End Date:
21 September 2002
Publisher
Name*:
Springer
URL:
http://www.springer.de/
Address*:
Berlin, Germany
Type:
Full paper
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
2461
Number:
Month:
September
Pages:
42-53
Year*:
2002
VG Wort Pages:
ISBN/ISSN:
0302-9743
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) 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.
URL for the Abstract:
http://link.springer.de/link/service/series/0558/bibs/2461/24610042.htm
Keywords:
Computational Geometry
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
Expert
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Rahul2002b,
AUTHOR = {Agarwal, Pankaj and Hagerup, Torben and Ray, Rahul and Sharir, Micha and Smid, Michiel and Welzl, Emo},
 EDITOR = {M{\"o}hring, Rolf and Raman, Rajeev},
 TITLE = {Translating a Planar Object to Maximize Point Containment},
 BOOKTITLE = {Algorithms - ESA 2002 : 10th Annual European Symposium},
 PUBLISHER = {Springer},
 YEAR = {2002},
 TYPE = {Full paper},
 ORGANIZATION = {EATCS},
 VOLUME = {2461},
 PAGES = {42--53},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Rome, Italy},
 MONTH = {September},
 ISBN = {0302-9743},
}

Entry last modified by Uwe Brahm, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Ray Rahul		Created
12/04/2002 04:37:33 PM
Revisions
11.
10.
9.
8.
7.		Editor(s)
Uwe Brahm
Uwe Brahm
Christine Kiesel
Christine Kiesel
Christine Kiesel		Edit Dates
02/14/2005 09:45:27 PM
02/14/2005 09:45:11 PM
08.09.2003 16:20:16
27.08.2003 14:41:45
26.08.2003 16:08:58