Simple multi-pass streaming algorithms for skyline points and extreme points

DOI10.4230/LIPICS.STACS.2021.22MaRDI QIDQ7231545zbMATH OpenFDO

Authors Timothy M. Chan, Saladi Rahul

Publication date 21 April 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2021.22

zbMATH Keywords

convex hullextreme pointsmulti-pass streaming algorithmsrandomized algorithmsskyline

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A new procedure for identifying the frame of the convex hull of a finite collection of points in multidimensional space
• Applications of random sampling in computational geometry. II
• Enumerating extreme points in higher dimensions
• Fast computation of output-sensitive maxima in a word RAM
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• Improved deterministic algorithms for linear programming in low dimensions
• Instance-optimal geometric algorithms
• Las Vegas algorithms for linear and integer programming when the dimension is small
• Multi-pass geometric algorithms
• Orthogonal range searching on the RAM, revisited
• Output-sensitive results on convex hulls, extreme points, and related problems
• Output-sensitive skyline algorithms in external memory
• Primal dividing and dual pruning: Output-sensitive construction of four-dimensional polytopes and three-dimensional Voronoi diagrams
• Small-dimensional linear programming and convex hulls made easy
• Streaming algorithms for planar convex hulls
• The Ultimate Planar Convex Hull Algorithm?

This page was built for publication: Simple multi-pass streaming algorithms for skyline points and extreme points

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