Marked Ancestor Problems (Preliminary Version)

  • Stephen Alstrup
  • Thore Husfeldt
  • Theis Rauhe

Abstract

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.
Published
1998-01-07
How to Cite
Alstrup, S., Husfeldt, T., & Rauhe, T. (1998). Marked Ancestor Problems (Preliminary Version). BRICS Report Series, 5(7). https://doi.org/10.7146/brics.v5i7.19279