---
res:
bibo_abstract:
- 'The batched static version of a searching problem asks for performing a given
set of queries on a given set of objects. All queries are known in advance. The
batched dynamic version of a searching problem is the following: given a sequence
of insertions, deletions, and queries, perform them on an initially empty set.
We will develop methods for solving batched static and batched dynamic versions
of searching problems which are in particular applicable to decomposable searching
problems. The techniques show that batched static (dynamic) versions of searching
problems can often be solved more efficiently than by using known static (dynamic)
data structures. In particular, a technique called “streaming” is described that
reduces the space requirements considerably. The methods have also a number of
applications on set problems. E.g., the k intersecting pairs in a set of n axis-parallel
hyper-rectangles in d dimensions can be reported in O (nlogd−1n + k) time using
only O(n) space.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Herbert
foaf_name: Edelsbrunner, Herbert
foaf_surname: Edelsbrunner
foaf_workInfoHomepage: http://www.librecat.org/personId=3FB178DA-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-9823-6833
- foaf_Person:
foaf_givenName: Mark
foaf_name: Overmars, Mark
foaf_surname: Overmars
bibo_doi: 10.1016/0196-6774(85)90030-6
bibo_issue: '4'
bibo_volume: 6
dct_date: 1985^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0196-6774
- http://id.crossref.org/issn/1090-2678
dct_language: eng
dct_publisher: Elsevier@
dct_title: Batched dynamic solutions to decomposable searching problems@
...