I am looking for state-of-the-art results on dynamic dominance reporting. In the dynamic dominance reporting problem, we have a set of k dimensional points and the goal is to maintain a data structure under insertions and deletions of points. The data structure is used to find the count of/enumerate all points that are dominated by a given query point.

A quick search on Google scholar shows a lot of results on dynamic orthogonal range reporting but I wasn't able to find much for the dynamic dominance reporting setting. A recent paper shows result for dynamic dominance reporting when $k=2$. Are there any algorithms/lower bounds known for general $k$ (or even $k \geq 3$)?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.