Une structure de données très rapide pour manipuler une frontière Paréto?

Sans forcement faire d'optimisation multi-objectif, j'ai souvent eu besoin de stocker n
valeurs qui satisfont les contraintes:
v1 <= v2 <= v3 .... <= vn
p1 <= p2 <= p3 .... <= pn

Ce besoin peut apparaître même dans la résolution du problème
de sac-à-dos par programmation dynamique; les v_i peuvent représenter
les valeurs et les p_i les poids. On a besoin de considérer un poids p supérieur
à un poids existant p_i uniquement si sa valeur v est aussi supérieure
à v_i.

Contrairement à un problème multi-objectif, on peut facilement arriver
à des frontières Paréto comme les (v_i, p_i) plus haut avec n=10000000.
Il peut devenir très cher de tester si une nouvelle paire (p,v) doit
faire partir de la frontière.

Quelqu'un connait une bibliothèque qui nous mets à disposition une structure
de données très rapide pour ce genre de taches?

A+,
Daniel