TY - JOUR AU - Alstrup, Stephen AU - Husfeldt, Thore AU - Rauhe, Theis PY - 1998/01/07 Y2 - 2024/03/29 TI - Marked Ancestor Problems (Preliminary Version) JF - BRICS Report Series JA - BRICS VL - 5 IS - 7 SE - Articles DO - 10.7146/brics.v5i7.19279 UR - https://tidsskrift.dk/brics/article/view/19279 SP - AB - 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.<br /> 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.<br /> 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. ER -