Data Structure to filter all pairwise-greater points?

Question

What is a good implementation of the following?

The data structure in question must not contain any point that is pairwise-greater-than another. e.g. (2,11) > (1,10), (5, 5) not-gt (1,5). And inputs occur online, so they cannot be pre-ordered/prepared.

Alright, this can be shown with the image above. So, each point is inserted in the order indicated, as follows:

1. (2,2) inserted
2. (2,4) inserted, not > (2,2) and vice versa so both remain
3. (3,3) > (2,2) and so is not inserted
4. (1,1); all others > so (1,1) inserted while all others removed

Ideas?

Answer 1

Start with the array of points (-Inf, Inf) and (Inf, -Inf)

Order the elements in array with respect to below rule

for (x,y) and (t,z)
if x<t (x,t) is before (t,z)
if x=t and y>z then (x,t) is before (t,z)

When you want to insert an element, find the element with highest order that is before the inserted element and call it EBefore. Also find the element with lowest order which is after the inserted element and call it EAfter. You may use binary search while finding these two elements.

If vectoral product of

EInserted x (EAfter - EBefore) > 0

remove the all the elemets between EBefore and EAfter and insert EInserted between them. If the product is negative then do not add the element.