An online algorithm to maintain the Pareto frontier elements

Question

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.

Answer 1

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.