An online algorithm to maintain the Pareto frontier elements

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.