GPU-friendly, Parallel, and (Almost-)In-Place Construction of Left-Balanced k-d Trees

2022/10/31 by Ingo Wald, Wald, Ingo · 1 citation
Computer Science · #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Theory and Algorithms #Graphics (cs.GR) #Parallel Computing and Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2211.00120

openalex publication_date 2022/10/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present an algorithm that allows for building left-balanced and complete k-d trees over k-dimensional points in a trivially parallel and GPU friendly way. Our algorithm requires exactly one int per data point as temporary storage, and uses O(log N) iterations, each of which performs one parallel sort, and one trivially parallel CUDA per-node update kernel.

Cited by

• A Generalizable Light Transport 3D Embedding for Global Illumination

Related

• Building a Balanced k-d Tree with MapReduce
• Building a Balanced k-d Tree in O(kn log n) Time
• A Stack-Free Traversal Algorithm for Left-Balanced k-d Trees
• Computing Treewidth on the GPU
• Parallel kd-tree with Batch Updates