Imagen de Portada

Tight Universal Bounds for Partially Presorted Pareto Front and Convex Hull

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	van der Hoog, Ivor, Rotenberg, Eva, Rutschmann, Daniel
Formato:	Preprint
Publicado:	2025
Materias:	Computational Geometry Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Instance and Universally Optimal Bounds for Imprecise Pareto Fronts
por: de Berg, Sarita, et al.
Publicado: (2026)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Dynamic Convex Hulls for Simple Paths
por: Brewer, Bruce, et al.
Publicado: (2024)

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

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

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

The Impossibility of Simultaneous Time and I/O Optimality for The Planar Maxima and Convex Hull Problems
por: Afshani, Peyman, et al.
Publicado: (2026)

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

Private Approximations of a Convex Hull in Low Dimensions
por: Gao, Yue, et al.
Publicado: (2020)

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

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

Making Quickhull More Like Quicksort: A Simple Randomized Output-Sensitive Convex Hull Algorithm
por: Goodrich, Michael T., et al.
Publicado: (2024)

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

ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs
por: An, Shinwoo, et al.
Publicado: (2024)

Tight Parameterized (In)tractability of Layered Crossing Minimization: Subexponential Algorithms and Kernelization
por: Fomin, Fedor V., et al.
Publicado: (2025)

Shortest Paths on Convex Polyhedral Surfaces
por: Wang, Haitao
Publicado: (2025)

Online Sorting and Translational Packing of Convex Polygons
por: Aamand, Anders, et al.
Publicado: (2021)

Maximum Independent Sets in Disk Graphs with Disks in Convex Position
por: Tkachenko, Anastasiia, et al.
Publicado: (2026)

Computing Dominating Sets in Disk Graphs with Centers in Convex Position
por: Tkachenko, Anastasiia, et al.
Publicado: (2026)

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

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

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

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

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
por: Kisfaludi-Bak, Sándor, et al.
Publicado: (2020)

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