Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Institute: MPI für Informatik     Collection: Algorithms and Complexity Group     Display Documents



ID: 202060.0, MPI für Informatik / Algorithms and Complexity Group
Translating a Planar Object to Maximize Point Containment
Authors:Agarwal, Pankaj; Hagerup, Torben; Ray, Rahul; Sharir, Micha; Smid, Michiel; Welzl, Emo
Editors:Möhring, Rolf; Raman, Rajeev
Language:English
Publisher:Springer
Place of Publication:Berlin, Germany
Date of Publication (YYYY-MM-DD):2002
Title of Proceedings:Algorithms - ESA 2002 : 10th Annual European Symposium
Start Page:42
End Page:53
Title of Series:Lecture Notes in Computer Science
Place of Conference/Meeting:Rome, Italy
(Start) Date of Conference/Meeting
 (YYYY-MM-DD):
2002-09-17
Review Status:not specified
Audience:Experts Only
Intended Educational Use:No
Abstract / Description: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.
Last Change of the Resource (YYYY-MM-DD):2003-09-08
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Kurt Mehlhorn
Affiliations:MPI für Informatik/Algorithms and Complexity Group
Identifiers:ISSN:0302-9743
LOCALID:C1256428004B93B8-DEDAEE38A05F3663C1256C850055D604-...
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.