Cover Image

Instance and Universally Optimal Bounds for Imprecise Pareto Fronts

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	de Berg, Sarita, Bække, Nynne Maria Foldager, Eriksen, Frida Astrup, van der Hoog, Ivor, Rotenberg, Eva, Rutschmann, Daniel
Format:	Preprint
Published:	2026
Subjects:	Computational Geometry Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Tight Universal Bounds for Partially Presorted Pareto Front and Convex Hull
by: van der Hoog, Ivor, et al.
Published: (2025)

Simpler Universally Optimal Dijkstra
by: van der Hoog, Ivor, et al.
Published: (2025)

Instance-Optimal Imprecise Convex Hull
by: de Berg, Sarita, et al.
Published: (2025)

Efficient Greedy Discrete Subtrajectory Clustering
by: van der Hoog, Ivor, et al.
Published: (2025)

The Contiguous Art Gallery Problem is in Θ(n log n)
by: de Berg, Sarita, et al.
Published: (2025)

Tight Better-Than-Worst-Case Bounds for Element Distinctness and Set Intersection
by: van der Hoog, Ivor, et al.
Published: (2025)

Simpler Optimal Sorting from a Directed Acyclic Graph
by: van der Hoog, Ivor, et al.
Published: (2024)

Near-Optimal Heaps and Dijkstra on Pointer Machines
by: van der Hoog, Ivor, et al.
Published: (2026)

A dynamic $(1+\varepsilon)$-spanner for disk intersection graphs
by: de Berg, Sarita, et al.
Published: (2026)

On computing the (exact) Fréchet distance with a frog
by: Conradi, Jacobus, et al.
Published: (2025)

Engineering Fully Dynamic Convex Hulls
by: van der Hoog, Ivor, et al.
Published: (2026)

Data Structures for Approximate Discrete Fréchet Distance
by: van der Hoog, Ivor, et al.
Published: (2022)

Near-tight Bounds for Computing the Fréchet Distance in d-Dimensional Grid Graphs and the Implications for λ-low Dense Curves
by: Conradi, Jacobus, et al.
Published: (2026)

Tight Bounds for Sorting Under Partial Information
by: van der Hoog, Ivor, et al.
Published: (2024)

A Combinatorial Proof of Universal Optimality for Computing a Planar Convex Hull
by: van der Hoog, Ivor, et al.
Published: (2025)

Dynamic Indexing Through Learned Indices with Worst-case Guarantees
by: Gæde, Emil Toftegaard, et al.
Published: (2025)

The Presort Hierarchy for Geometric Problems
by: van der Hoog, Ivor, et al.
Published: (2026)

Local Density and its Distributed Approximation
by: Christiansen, Aleksander Bjørn, et al.
Published: (2024)

From Theory to Practice: Engineering Approximation Algorithms for Dynamic Orientation
by: Großmann, Ernestine, et al.
Published: (2025)

The Complexity of Geodesic Spanners
by: de Berg, Sarita, et al.
Published: (2023)

Sorting under Partial Information with Optimal Preprocessing Time via Unified Bound Heaps
by: Rutschmann, Daniel
Published: (2026)

Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain
by: de Berg, Sarita, et al.
Published: (2023)

Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation
by: Bringmann, Karl, et al.
Published: (2024)

The Complexity of Geodesic Spanners using Steiner Points
by: de Berg, Sarita, et al.
Published: (2024)

Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
by: de Berg, Mark, et al.
Published: (2026)

Optimal Bounds for Spanners and Tree Covers in Doubling Metrics
by: La, An, et al.
Published: (2025)

Simpler is Faster: Practical Distance Reporting by Sorting Along a Space-Filling Curve
by: de Berg, Sarita, et al.
Published: (2025)

Towards Instance-Optimal Euclidean Spanners
by: Le, Hung, et al.
Published: (2024)

Practical Insertion-Only Convex Hull
by: van der Hoog, Ivor, et al.
Published: (2025)

On the Discrete Fréchet Distance in a Graph
by: Driemel, Anne, et al.
Published: (2022)

Near-Optimal Bounds for Parameterized Euclidean k-means
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Pareto Sums of Pareto Sets: Lower Bounds and Algorithms
by: Funke, Daniel, et al.
Published: (2024)

Upward-Planar Drawings with Bounded Span
by: Angelini, Patrizio, et al.
Published: (2026)

Weakly Leveled Planarity with Bounded Span
by: Bekos, Michael, et al.
Published: (2024)

Nearly-Tight Bounds for Zonotope Containment and Beyond
by: Eisenbrand, Friedrich, et al.
Published: (2026)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
by: Cohen-Addad, Vincent, et al.
Published: (2026)

New Complexity and Algorithmic Bounds for Minimum Consistent Subsets
by: Banik, Aritra, et al.
Published: (2024)

Tight Bounds on the Number of Closest Pairs in Vertical Slabs
by: Biniaz, Ahmad, et al.
Published: (2025)

Coresets for Constrained Clustering: General Assignment Constraints and Improved Size Bounds
by: Huang, Lingxiao, et al.
Published: (2023)

Optimal Orthogonal Drawings in Linear Time
by: Didimo, Walter, et al.
Published: (2025)