Marked Ancestor Problems

Consider a rooted tree whose nodes can be in two states: marked or unmarked. The marked ancestor problem is to maintain a data structure with the following operations: mark(v) marks node v: unmark(v) removes any marks from node v; firstmarked(v) returns the first marked node on the path from v to the root. We show tight upper and lower bounds for the marked ancestor problem. The lower bounds are proved in the cell probe model, the algorithms 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 segment intersection, interval maintenance, and ray shooting in the plane. Our upper bounds improve algorithms from various fields, including coloured ancestor problems and maintenance of balanced parentheses.

Authors

• Stephen Alstrup
• Thore Husfeldt
• Theis Rauhe

Keywords

• Read only memory
• Upper bound
• DNA
• Computational geometry
• Data structures
• Probes
• Marked Ancestor
• Data Structure
• Lower Bound
• Unmarked
• Emptiness
• Existence Of Problems
• Ray Casting
• Time Constant
• Proof Of Theorem
• Tree Nodes
• Linear Time
• Time Stamp
• Dynamic Problem
• Tree Level
• Linear Space
• Probability 1
• Substring
• Update Operation
• Priority Queue
• Query Time
• Worst-case Time
• Update Time
• Boolean Function
• Word Size
• Preprocessing Time