Instance-optimal imprecise convex hull

DOI10.4230/LIPICS.ESA.2025.25MaRDI QIDQ7322414zbMATH OpenFDO

Authors Sarita de Berg, Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann, Sampson Wong

Publication date 31 August 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2025.25

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• Balancing poset extensions
• Bidirectional Dijkstra's algorithm is instance-optimal
• Computational geometry. Algorithms and applications.
• Convex hull of points lying on lines in \(O(n\log n)\) time after preprocessing
• Delaunay triangulation of imprecise points in linear time after preprocessing
• Delaunay triangulations in O (sort( n )) time and more
• Efficient update strategies for geometric computing with uncertainty
• Fast and simple sorting using partial information
• scientific article; zbMATH DE number 6693709 (Why is no real title available?)
• Instance-optimal geometric algorithms
• Preprocessing Ambiguous Imprecise Points
• Preprocessing Imprecise Points and Splitting Triangulations
• Preprocessing imprecise points for Delaunay triangulation: simplified and extended
• Simpler optimal sorting from a directed acyclic graph
• Sorting under partial information (without the ellipsoid algorithm).
• Tight bounds for sorting under partial information
• Triangulating input-constrained planar point sets
• Unions of onions: preprocessing imprecise points for fast onion layer decomposition

This page was built for publication: Instance-optimal imprecise convex hull

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7322414)