文章基本信息

标题：Marked Ancestor Problems (Preliminary Version)
本地全文：下载
作者：Stephen Alstrup ; Thore Husfeldt ; Theis Rauhe 等
期刊名称：BRICS Report Series
印刷版ISSN：0909-0878
出版年度：1998
卷号：5
期号：7
出版社：Aarhus University
摘要：Consider a rooted tree whose nodes can be marked or unmarked. Given a node, we want to find its nearest marked ancestor. This generalises the well-known predecessor problem, where the tree is a path. We show tight upper and lower bounds for this problem. The lower bounds are proved in the cell probe model, the upper bounds run on a unit-cost RAM. As easy corollaries we prove (often optimal) lower bounds on a number of problems. These include planar range searching, including the existential or emptiness problem, priority search trees, static tree union-find, and several problems from dynamic computational geometry, including intersection problems, proximity problems, and ray shooting. Our upper bounds improve a number of algorithms from various fields, including dynamic dictionary matching and coloured ancestor problems.