3
$\begingroup$

I'm looking for an online algorithm/datastructure that is able to maintain a pareto frontier for two dimensional elements in an online scenario where elements can be added and deleted.

For example:

  • insert((3,7))

    • since the pareto front is empty it has to be added to it
    • set of elements E={(3,7)}
    • pareto frontier P={(3,7)}
  • insert((7,3)) and insert((10,2))

    • both have to be added to pareto frontier (since they arent dominated)
    • set of elements E={(3,7), (7,3), (10,2)}
    • pareto frontier P={(3,7), (7,3), (10,2)}
  • insert((8,4))

    • is dominated by (7,3) so do not add it to the pareto frontier (but keep it in the set of elements E because its maybe going to be part of the pareto frontier later)
    • set of elements E={(3,7), (7,3), (10,2), (8,4)}
    • pareto frontier P={(3,7), (7,3), (10,2)}
  • remove((7,3))

    • remove (7,3) from the set of elements and from the pareto frontier. The pareto frontier has to adjust accordingly and therefore (8,4) is added to the pareto frontier now.
    • set of elements E={(3,7), (10,2), (8,4)}
    • pareto frontier P={(3,7), (10,2), (8,4)}

This question is similiar to An online algorithm to find the Pareto frontier elements, but in the scenario described above points can also be removed. A brute force algorithm would have quadratic time complexity and I am looking for something better.

$\endgroup$
2
$\begingroup$

You can find an answer to this in "Dynamic Planar Range Maxima Queries", by Brodal and Tsakalidis. They support insert and remove in $O(\log n)$ time. That paper points to several previous papers that addressed the question as well.

In particular, I expect the simplest solution can be found in sections 8 and 9 of "Maintenance of Configurations in the Plane", Technical Report RUU-CS-79-9, by Overmars and van Leeuwen, (mirror). Their solution takes $O(\log^2 n)$ for each insert or remove.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.