Streaming algorithms for planar convex hulls

DOI10.4230/LIPICS.ISAAC.2018.47MaRDI QIDQ5091039zbMATH OpenFDO

Authors Martin Farach-Colton, Meng Li, Meng-Tsung Tsai

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1810.00455

zbMATH Keywords

convex hullslower boundsstreaming algorithms

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Approximate convex hull of data streams
• Geometric streaming algorithm with A sorting primitive
• Geometric Streaming Algorithms with a Sorting Primitive
• Streaming algorithms for line simplification
• Optimal time-space tradeoff for the 2D convex-hull problem

Cites work

• Adapting parallel algorithms to the W-stream model, with applications to graph problems
• Adaptive sampling for geometric problems over data streams
• An O(n\log ^2 h) Time Algorithm for the Three-Dimensional Convex Hull Problem
• An efficient algorithm for determining the convex hull of a finite planar set
• Another efficient algorithm for convex hulls in two dimensions
• Convex hulls of finite sets of points in two and three dimensions
• EFFICIENT APPROXIMATION OF CONVEX POLYGONS
• Hausdorff approximation of convex polygons
• Maintenance of configurations in the plane
• Multi-pass geometric algorithms
• On a Simple, Practical, Optimal, Output-Sensitive Randomized Planar Convex Hull Algorithm
• On the identification of the convex hull of a finite set of points in the plane
• Optimal output-sensitive convex hull algorithms in two and three dimensions
• Optimal parallel algorithms for computing convex hulls and for sorting
• Optimal, output-sensitive algorithms for constructing planar hulls in parallel
• Space-efficient geometric divide-and-conquer algorithms
• Space-efficient planar convex hull algorithms
• The complexity of incremental convex hull algorithms in \(R^ d\)
• The Probabilistic Communication Complexity of Set Intersection
• The quickhull algorithm for convex hulls
• The Ultimate Planar Convex Hull Algorithm?
• Tight Lower Bounds for Multi-pass Stream Computation Via Pass Elimination
• Trading off space for passes in graph streaming problems

Cited in

(5)

• Streaming algorithms for extent problems in high dimensions
• Streaming Algorithms for Smallest Intersecting Ball of Disjoint Balls
• scientific article; zbMATH DE number 6297803 (Why is no real title available?)
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Simple multi-pass streaming algorithms for skyline points and extreme points

This page was built for publication: Streaming algorithms for planar convex hulls

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