Cache-Oblivious Parallel Convex Hull in the Binary Forking Model

2023/05/17 by Reilly Browne, Rezaul Chowdhury, Browne, Reilly +5
Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Privacy-Preserving Technologies in Data

paper · pdf · doi:10.48550/arxiv.2305.10389

openalex publication_date 2023/05/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present two cache-oblivious sorting-based convex hull algorithms in the Binary Forking Model. The first is an algorithm for a presorted set of points which achieves O(n) work, O(log n) span, and O(n/B) serial cache complexity, where B is the cache line size. These are all optimal worst-case bounds for cache-oblivious algorithms in the Binary Forking Model. The second adapts Cole and Ramachandran's cache-oblivious sorting algorithm, matching its properties including achieving O(n log n) work, O(log n log log n) span, and O(n/B log_M n) serial cache complexity. Here M is the size of the private cache.

Related

• Efficient cache oblivious algorithms for randomized divide-and-conquer on the multicore model
• SquareSort: a cache-oblivious sorting algorithm
• Data Oblivious Algorithms for Multicores
• Balanced Partitioning of Several Cache-Oblivious Algorithms
• Memory-Adjustable Navigation Piles with Applications to Sorting and Convex Hulls