MPI-I-91-112
An optimal construction method for generalized convex layers
Lenhof, Hans-Peter and Smid, Michiel
August 1991, 25 pages.
.
Status: available - back from printing
Let $P$ be a set of $n$ points in the Euclidean plane
and let $C$ be a convex figure.
In 1985, Chazelle and Edelsbrunner presented an algorithm,
which preprocesses $P$ such that for any query point $q$,
the points of $P$ in the translate $C+q$ can be retrieved
efficiently. Assuming that constant time suffices for deciding
the inclusion of a point in $C$, they provided
a space and query time optimal solution. Their algorithm
uses $O(n)$ space. A~query with output size $k$ can be solved in
$O(\log n + k)$ time.
The preprocessing step of their algorithm, however,
has time complexity $O(n^2)$.
We show
that the usage of a new construction method for layers
reduces the preprocessing time to $O(n \log n)$. We thus
provide the first space, query time and preprocessing time
optimal solution for this class of point retrieval problems.
Besides, we present two new dynamic data structures
for these problems. The
first dynamic data structure allows on-line insertions
and deletions of points in
$O((\log n)^2)$ time. In this dynamic data
structure, a query with output size~$k$ can be solved in
$O(\log n + k(\log n)^2)$ time.
The second dynamic data structure, which allows only
semi-online updates, has $O((\log n)^2)$ amortized
update time and $O(\log n+k)$ query time.
-
- Attachement: MPI-I-91-112.pdf (13846 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1991-112
BibTeX
@TECHREPORT{LenhofSmid91,
AUTHOR = {Lenhof, Hans-Peter and Smid, Michiel},
TITLE = {An optimal construction method for generalized convex layers},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-91-112},
MONTH = {August},
YEAR = {1991},
ISSN = {0946-011X},
}