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(upsilon) marks node upsilon; unmark(upsilon) removes any marks from node upsilon; firstmarked(upsilon) returns the first marked node on the path from upsilon 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 an a unit-cost RAM. As easy corollaries Ive 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.