Instance Optimal and Universally Optimal Bounds for Imprecise Pareto Fronts

In the imprecise geometry model, the input is a family of regions F = (R1, R2, . . ., Rn), each containing a point pi ∈ Ri. The task is then to compute some function of the points p1, p2, . . . pn, in our case an implicit representation of their Pareto front. To this end, one may query a region Ri to retrieve its contained point pi ∈ Ri. In this model, efficiency is interpreted in two ways: minimizing (i) the number of retrievals, and (ii) the computation time both for preprocessing, and the execution of the query stage, i.e. for computing which points to query and constructing the output. We present an algorithm to construct (an implicit representation of) the Pareto front for possibly overlapping rectangles, that is instance-optimal with respect to the number of retrievals. This means that for every fixed input (F, P), there is no algorithm that retrieves asymptotically fewer regions to compute the output. This is a strong algorithmic quality, as it means that our algorithm is competitive even to clairvoyant algorithms which only have to verify the correctness of a correct guess. In terms of algorithmic running time, instance-optimality is provably unobtainable. We instead present an algorithm which is within a log n-factor of instance optimality. This generalizes earlier results which assumed the regions to not overlap, at only a minor cost in running time. For unit squares, we present an algorithm that is not only instance optimal in the number of retrievals, but also universally optimal in terms of running time. This means that for any fixed set of regions F, no algorithm has a better worst-case running time for all possible point sets P. Thus, this work presents the first universally optimal algorithm for overlapping planar input. Compared to previous work, our result improves the degree to which the input regions may overlap, the preprocessing time, the number of retrievals, and the running time.