---
OA_place: publisher
OA_type: gold
_id: '22916'
abstract:
- lang: eng
  text: "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. \r\nWe 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. \r\nFor 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."
acknowledgement: This work was supported by the the VILLUM Foundation grant (VIL37507)
  "Efficient Recomputations for Changeful Problems".
alternative_title:
- LIPIcs
article_number: '106'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Sarita
  full_name: De Berg, Sarita
  last_name: De Berg
- first_name: Nynne Maria Foldager
  full_name: Bække, Nynne Maria Foldager
  last_name: Bække
- first_name: Frida Astrup
  full_name: Eriksen, Frida Astrup
  last_name: Eriksen
- first_name: Ivor
  full_name: Van Der Hoog, Ivor
  last_name: Van Der Hoog
- first_name: Eva
  full_name: Rotenberg, Eva
  last_name: Rotenberg
- first_name: Daniel P
  full_name: Rutschmann, Daniel P
  id: 7397d908-b582-11f0-bf73-88b902e86527
  last_name: Rutschmann
citation:
  ama: 'De Berg S, Bække NMF, Eriksen FA, Van Der Hoog I, Rotenberg E, Rutschmann
    DP. Instance optimal and universally optimal bounds for imprecise pareto fronts.
    In: <i>34th Annual European Symposium on Algorithms</i>. Vol 388. Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik; 2026. doi:<a href="https://doi.org/10.4230/LIPIcs.ESA.2026.106">10.4230/LIPIcs.ESA.2026.106</a>'
  apa: 'De Berg, S., Bække, N. M. F., Eriksen, F. A., Van Der Hoog, I., Rotenberg,
    E., &#38; Rutschmann, D. P. (2026). Instance optimal and universally optimal bounds
    for imprecise pareto fronts. In <i>34th Annual European Symposium on Algorithms</i>
    (Vol. 388). L’Aquila, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
    <a href="https://doi.org/10.4230/LIPIcs.ESA.2026.106">https://doi.org/10.4230/LIPIcs.ESA.2026.106</a>'
  chicago: De Berg, Sarita, Nynne Maria Foldager Bække, Frida Astrup Eriksen, Ivor
    Van Der Hoog, Eva Rotenberg, and Daniel P Rutschmann. “Instance Optimal and Universally
    Optimal Bounds for Imprecise Pareto Fronts.” In <i>34th Annual European Symposium
    on Algorithms</i>, Vol. 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2026. <a href="https://doi.org/10.4230/LIPIcs.ESA.2026.106">https://doi.org/10.4230/LIPIcs.ESA.2026.106</a>.
  ieee: S. De Berg, N. M. F. Bække, F. A. Eriksen, I. Van Der Hoog, E. Rotenberg,
    and D. P. Rutschmann, “Instance optimal and universally optimal bounds for imprecise
    pareto fronts,” in <i>34th Annual European Symposium on Algorithms</i>, L’Aquila,
    Italy, 2026, vol. 388.
  ista: 'De Berg S, Bække NMF, Eriksen FA, Van Der Hoog I, Rotenberg E, Rutschmann
    DP. 2026. Instance optimal and universally optimal bounds for imprecise pareto
    fronts. 34th Annual European Symposium on Algorithms. ESA: European Symposium
    on Algorithms, LIPIcs, vol. 388, 106.'
  mla: De Berg, Sarita, et al. “Instance Optimal and Universally Optimal Bounds for
    Imprecise Pareto Fronts.” <i>34th Annual European Symposium on Algorithms</i>,
    vol. 388, 106, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a
    href="https://doi.org/10.4230/LIPIcs.ESA.2026.106">10.4230/LIPIcs.ESA.2026.106</a>.
  short: S. De Berg, N.M.F. Bække, F.A. Eriksen, I. Van Der Hoog, E. Rotenberg, D.P.
    Rutschmann, in:, 34th Annual European Symposium on Algorithms, Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik, 2026.
conference:
  end_date: 2026-09-04
  location: L’Aquila, Italy
  name: 'ESA: European Symposium on Algorithms'
  start_date: 2026-08-31
corr_author: '1'
das_tickbox: '0'
date_created: 2026-09-13T22:01:52Z
date_published: 2026-08-25T00:00:00Z
date_updated: 2026-09-16T08:59:49Z
day: '25'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2026.106
external_id:
  arxiv:
  - '2605.07523'
file:
- access_level: open_access
  checksum: 75cfae9e9773be4b06f9aab66041f0f3
  content_type: application/pdf
  creator: dernst
  date_created: 2026-09-16T08:58:04Z
  date_updated: 2026-09-16T08:58:04Z
  file_id: '22935'
  file_name: 2026_LIPIcsESA_deBerg.pdf
  file_size: 1102214
  relation: main_file
  success: 1
file_date_updated: 2026-09-16T08:58:04Z
fulldoi: https://doi.org/10.4230/LIPIcs.ESA.2026.106
has_accepted_license: '1'
intvolume: '       388'
keyword:
- Pareto front
- imprecise geometry
- instance optimality
- universal optimality
- preprocessing model
- partial information
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
publication: 34th Annual European Symposium on Algorithms
publication_identifier:
  isbn:
  - '9783959774451'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Instance optimal and universally optimal bounds for imprecise pareto fronts
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 388
year: '2026'
...