Pith Number

pith:4ZVW6MCY

pith:2026:4ZVW6MCYX4KA67M4ZQLIHII6QB

not attested not anchored not stored refs resolved

Instance and Universally Optimal Bounds for Imprecise Pareto Fronts

Daniel Rutschmann, Eva Rotenberg, Frida Astrup Eriksen, Ivor van der Hoog, Nynne Maria Foldager B{\ae}kke, Sarita de Berg

An algorithm computes the Pareto front of imprecise overlapping rectangles by retrieving only the minimal number of exact points needed for any given input.

arxiv:2605.07523 v1 · 2026-05-08 · cs.CG · cs.DS

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{4ZVW6MCYX4KA67M4ZQLIHII6QB}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

We present an algorithm to construct the Pareto front for possibly overlapping rectangles that is instance-optimal with respect to the number of retrievals, meaning that for every fixed input (F, P), there is no algorithm that retrieves asymptotically fewer regions to compute the output.

C2weakest assumption

The input consists of axis-aligned rectangles or unit squares in the plane and the Pareto front is defined via standard 2D dominance; the model assumes that retrieving a point from its region is the only way to resolve its exact position.

C3one line summary

Instance-optimal retrieval algorithms for Pareto fronts of overlapping imprecise rectangles, plus universally optimal time bounds for unit squares.

References

13 extracted · 13 resolved · 0 Pith anchors

[1] Jallu, Vahideh Keikha, Maarten Löffler, and Maria Saumell 2022 · doi:10.1016/j.tcs.2022.07.016

[2] 4 Sarita de Berg, Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann, and Sampson Wong 2025 · doi:10.4230/lipics.esa.2025.25

[3] 5555/3235147 2005 · doi:10.1007/s00224-004-1180-4

[4] 10 Bernard Chazelle 1988 · doi:10.1137/0217026

[5] v2i1a3ff.ffinria-00595823 2026 · doi:10.20382/jocg

Formal links

2 machine-checked theorem links

Receipt and verification

First computed	2026-05-20T00:00:41.268263Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

e66b6f3058bf140f7d9ccc1683a11e80722fe578e48cd4cbfffabb947cc992c4

Aliases

arxiv: 2605.07523 · arxiv_version: 2605.07523v1 · doi: 10.48550/arxiv.2605.07523 · pith_short_12: 4ZVW6MCYX4KA · pith_short_16: 4ZVW6MCYX4KA67M4 · pith_short_8: 4ZVW6MCY

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/4ZVW6MCYX4KA67M4ZQLIHII6QB \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: e66b6f3058bf140f7d9ccc1683a11e80722fe578e48cd4cbfffabb947cc992c4

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "4a4a48f5cc25e041200ad1c90e8b7e843f664b25074acf75a92d970a99f6caf2",
    "cross_cats_sorted": [
      "cs.DS"
    ],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "cs.CG",
    "submitted_at": "2026-05-08T09:53:57Z",
    "title_canon_sha256": "8d06798e231e1bb484ea7b6a008a0c4d43850a490eb47657b8792a76cc75f194"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.07523",
    "kind": "arxiv",
    "version": 1
  }
}