Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

URL of the conference:

http://www.dis.uniroma1.it/~algo02/esa02/

URL for downloading the paper:

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section