ISSN:
1432-0541
Keywords:
Computational geometry
;
Linear lists
;
Dynamic data structures
;
Amortized complexity
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract The problem of searching for a key in many ordered lists arises frequently in computational geometry. Chazelle and Guibas recently introduced fractional cascading as a general technique for solving this type of problem. In this paper we show that fractional cascading also supports insertions into and deletions from the lists efficiently. More specifically, we show that a search for a key inn lists takes timeO(logN +n log logN) and an insertion or deletion takes timeO(log logN). HereN is the total size of all lists. If only insertions or deletions have to be supported theO(log logN) factor reduces toO(1). As an application we show that queries, insertions, and deletions into segment trees or range trees can be supported in timeO(logn log logn), whenn is the number of segments (points).
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01840386
