Struttura dati per filtrare tutti i punti maggiori a coppie?

Question

Qual è una buona implementazione di quanto segue?

La struttura dati in questione non deve contenere alcun punto che sia pairwise-maggiore di un altro. per esempio. (2,11)> (1,10), (5, 5) non-gt (1,5). E gli input si verificano online, quindi non possono essere preordinati/preparati.

Bene, questo può essere indicato con l'immagine di cui sopra. Quindi, ogni punto viene inserita nell'ordine indicato, come segue:

1. (2,2) inserita
2. (2,4) inserito, non> (2,2) e viceversa in modo che entrambi siano
3. (3,3)> (2,2) e quindi non inserito
4. (1,1); tutti gli altri> così (1,1) inseriti mentre tutti gli altri rimossi

Idee?

Answer 1

Elenco collegato singolarmente con punti che è pairwise-less di un altro.

Considerare la situazione dei confronti un nuovo punto per ciascun punto nell'elenco al passaggio corrente. Сheck: il nostro punto è inferiore a un punto di controllo nell'elenco?

In tal caso, rimuovere dal punto di controllo dell'elenco.

Altrimenti, è sufficiente aggiungere un nuovo punto all'elenco.

Alla fine, la lista ha tali punti.

Answer 2

Inizia con la matrice di punti (-Inf, INF) e (Inf, -Inf)

Ordinare gli elementi in serie rispetto al sottostante regola

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) 

Quando si desidera inserire un elemento, trova l'elemento con l'ordine più alto prima dell'elemento inserito e chiamalo EBefore. Trova anche l'elemento con l'ordine più basso che è dopo l'elemento inserito e chiamalo EAfter. Puoi usare la ricerca binaria mentre trovi questi due elementi.

Se il prodotto vettoriale di

EInserted x (EAfter - EBefore) > 0 

rimuovere le tutte le elemets tra EBefore e EDopo e inserire EInserted tra di loro. Se il prodotto è negativo, non aggiungere l'elemento.