Preprocessing Imprecise Points for the Pareto Front

The preprocessing model for uncertain data models geometric imprecision of algorithmic input and provides a framework for working with it. In this model, we are given a set of regions ℛ which model the uncertainty associated with an unknown set of points P. There are two phases: a preprocessing phase, in which we have access only to ℛ, followed by a reconstruction phase, in which we have access to points in P, possibly at a certain retrieval cost C per point. For a given algorithmic problem, the goal in this model is to perform as much of the necessary computations as possible in the preprocessing phase, so that the amount of time spent in the reconstruction phase is minimized. In this paper, we investigate the following algorithmic question: how fast can we compute the Pareto front of P in the preprocessing model? We show that if ℛ is a set of pairwise-disjoint axis-aligned rectangles then we can preprocess ℛ to reconstruct the Pareto front of P efficiently. In contrast to earlier work in the preprocessing model, our solution achieves sublinear reconstruction time when the output complexity is sublinear. 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. Our results are worst-case optimal, but we prove that instance optimality is unobtainable for a wide class of problems in the preprocessing model. We prove that, in fact, our results are uncertainty-region optimal with respect to real RAM instructions in the reconstruction phase.