2026-09-22T18:29:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27242 2026-09-05T20:16:26Z ddc:004 open_access

Instance Optimal and Universally Optimal Bounds for Imprecise Pareto Fronts de Berg, Sarita Bække, Nynne Maria Foldager Eriksen, Frida Astrup van der Hoog, Ivor Rotenberg, Eva Rutschmann, Daniel Pareto front imprecise geometry instance optimality universal optimality preprocessing model partial information In the imprecise geometry model, the input is a family of regions F = (R₁, R₂, …,R_n), each containing a point p_i ∈ R_i. The task is then to compute some function of the points p₁,p₂,… p_n, in our case an implicit representation of their Pareto front. To this end, one may query a region R_i to retrieve its contained point p_i ∈ R_i. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sarita de Berg and Nynne Maria Foldager Bække and Frida Astrup Eriksen and Ivor van der Hoog and Eva Rotenberg and Daniel Rutschmann 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.106 urn:nbn:de:0030-drops-272426 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.106 eng https://creativecommons.org/licenses/by/4.0/legalcode