  In the preprocessing model for uncertain data we are given a set of regions R
which model the uncertainty associated with an unknown set of points P. In this
model there are two phases: a preprocessing phase, in which we have access only
to R, followed by a reconstruction phase, in which we have access to points in
P at a certain retrieval cost C per point. We study the following algorithmic
question: how fast can we construct the pareto front of P in the preprocessing
model?
  We show that if R is a set of pairwise-disjoint axis-aligned rectangles, then
we can preprocess R to reconstruct the Pareto front of P efficiently. To refine
our algorithmic analysis, we introduce a new notion of algorithmic optimality
which relates to the entropy of the uncertainty regions. Our proposed
uncertainty-region optimality falls on the spectrum between worst-case
optimality and instance optimality. We prove that instance optimality is
unobtainable in the preprocessing model, whenever the classic algorithmic
problem reduces to sorting. Our results are worst-case optimal in the
preprocessing phase; in the reconstruction phase, our results are
uncertainty-region optimal with respect to real RAM instructions, and instance
optimal with respect to point retrievals.
