English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

An optimal construction method for generalized convex layers

MPS-Authors
/persons/resource/persons44909

Lenhof,  Hans-Peter
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45509

Smid,  Michiel
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

MPI-I-91-112.pdf
(Any fulltext), 14MB

Supplementary Material (public)
There is no public supplementary material available
Citation

Lenhof, H.-P., & Smid, M.(1991). An optimal construction method for generalized convex layers (MPI-I-91-112). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-7B11-A
Abstract
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.