Data structure for filtering all pairwise large points?

Question

What is a good implementation of the following?

The data structure in question should not contain any point that is pairwise larger than the other. e.g. (2.11)> (1.10), (5, 5) non-gt (1,5). And the entrances take place on the network, so they cannot be pre-ordered / prepared.

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

• (2.2) inserted
• (2.4), not> (2.2) and vice versa, so both remain
• (3.3)> (2.2) and therefore not inserted
• (1.1); all the others> are so (1,1) inserted, and the rest are deleted

Ideas?

Answer 1

Start with an array of dots (-Inf, Inf) and (Inf, -Inf)

The order of the elements in the array relative to the rule below

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) 

If you want to insert an element, find the element with the highest order that is before the inserted element and name it EBefore. Also find the element with the lowest order that is after the inserted element and calls it EAfter. You can use binary search when searching for these two elements.

If the vector product

 EInserted x (EAfter - EBefore) > 0 

delete all elements between EBefore and EAfter and insert EInserted between them. If the product is negative, do not add the item.

Answer 2

A single list with points that are pairwise smaller than the others.

Consider the situation of comparing a new point for each point in the list at the current step. Check: is our point less than the checkpoint in the list?

If so, remove the list from the checkpoint.

Otherwise, just add a new point to the list.

At the end, the list has such points.