Cover Image

Building a Balanced k-d Tree in O(kn log n) Time

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Brown, Russell A.
Format:	Preprint
Published:	2014
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Review of Three Algorithms That Build k-d Trees
by: Brown, Russell A.
Published: (2025)

A Dynamic, Self-balancing k-d Tree
by: Brown, Russell A.
Published: (2025)

Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time
by: Huang, Shang-En, et al.
Published: (2016)

Comparative Performance of the AVL Tree and Three Variants of the Red-Black Tree
by: Brown, Russell A.
Published: (2024)

Finding a solution to the Erdős-Ginzburg-Ziv theorem in $O(n\log\log\log n)$ time
by: Leung, Yui Hin Arvin
Published: (2025)

$O(\log n)$-Approximation Algorithms for Bipartiteness Ratio
by: Soma, Tasuku, et al.
Published: (2025)

On the Hardness Hierarchy for the $O(n \sqrt{\log n})$ Complexity in the Word RAM
by: Kempa, Dominik, et al.
Published: (2025)

Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$
by: Chang, Hsien-Chih, et al.
Published: (2024)

An $O(n \log n)$-Time Approximation Scheme for Geometric Many-to-Many Matching
by: Bandyapadhyay, Sayan, et al.
Published: (2024)

Fully dynamic biconnectivity in $\tilde{\mathcal{O}}(\log^2 n)$ time
by: Holm, Jacob, et al.
Published: (2025)

A simpler and parallelizable $O(\sqrt{\log n})$-approximation algorithm for Sparsest Cut
by: Kolmogorov, Vladimir
Published: (2023)

LZBE: an LZ-style compressor supporting $O(\log n)$-time random access
by: Shibata, Hiroki, et al.
Published: (2025)

An $O(n\log n)$ Algorithm for Single-Item Lot Sizing with a One-Breakpoint All-Units Discount and Non-Increasing Prices
by: Papadopoulos, Kleitos
Published: (2025)

An $\mathcal{O}(\log N)$ Time Algorithm for the Generalized Egg Dropping Problem
by: Papadopoulos, Kleitos
Published: (2026)

PCF Learned Sort: a Learning Augmented Sort Algorithm with $O(n \log\log n)$ Expected Complexity
by: Sato, Atsuki, et al.
Published: (2024)

Time Efficient Implementation for Online $k$-server Problem on Trees
by: Khadiev, Kamil, et al.
Published: (2024)

Distributionally Robust $k$-of-$n$ Sequential Testing
by: Tan, Rayen, et al.
Published: (2026)

Time-Optimal $k$-Server
by: Frei, Fabian, et al.
Published: (2025)

Weighted $k$-Path and Other Problems in Almost $O^*(2^k)$ Deterministic Time via Dynamic Representative Sets
by: Nederlof, Jesper
Published: (2025)

Solving Random Planted CSPs below the $n^{k/2}$ Threshold
by: Basu, Arpon, et al.
Published: (2025)

An $O(n^5)$-Time Algorithm for Optimal Broadcast Domination
by: Papadopoulos, Kleitos
Published: (2026)

The Contiguous Art Gallery Problem is in Θ(n log n)
by: de Berg, Sarita, et al.
Published: (2025)

Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More
by: Korhonen, Tuukka
Published: (2024)

Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time
by: Georgiadis, Loukas, et al.
Published: (2026)

Concurrent Balanced Augmented Trees
by: Wrench, Evan, et al.
Published: (2026)

Non-Adaptive Evaluation of $k$-of-$n$ Functions: Tight Gap and a Unit-Cost PTAS
by: Nielsen, Mads Anker, et al.
Published: (2025)

Deterministic $k$-Median Clustering in Near-Optimal Time
by: Costa, Martín, et al.
Published: (2025)

The planar edge-coloring theorem of Vizing in $O(n\log n)$ time
by: Jędrzejczak, Patryk, et al.
Published: (2025)

Space-efficient SLP encoding for $O(\log N)$-time random access
by: Takasaka, Akito, et al.
Published: (2024)

Sub-$n^k$ Deterministic algorithm for minimum $k$-way cut in simple graphs
by: Daga, Mohit
Published: (2025)

On Time-Memory Tradeoffs for Maximal Palindromes with Wildcards and $k$-Mismatches
by: Amir, Amihood, et al.
Published: (2026)

On Tight FPT Time Approximation Algorithms for k-Clustering Problems
by: Dai, Han, et al.
Published: (2025)

Learning Multinomial Logits in $O(n \log n)$ time
by: Chierichetti, Flavio, et al.
Published: (2026)

A $O^*((2 + ε)^k)$ Time Algorithm for Cograph Deletion Using Unavoidable Subgraphs in Large Prime Graphs
by: Lafond, Manuel, et al.
Published: (2026)

Fully Dynamic $k$-Clustering with Fast Update Time and Small Recourse
by: Bhattacharya, Sayan, et al.
Published: (2024)

Fully Dynamic k-Means Coreset in Near-Optimal Update Time
by: la Tour, Max Dupré, et al.
Published: (2024)

Fully Dynamic $k$-Median with Near-Optimal Update Time and Recourse
by: Bhattacharya, Sayan, et al.
Published: (2024)

An $Ω(n \log n)$ Randomized Lower Bound for Cutting a Cake into Proportionally Fair Pieces
by: Arndt, Stephen, et al.
Published: (2026)

The adaptive complexity of parallelized log-concave sampling
by: Zhou, Huanjian, et al.
Published: (2024)

On $k$-connectivity oracles in $k$-connected graphs
by: Nutov, Zeev
Published: (2026)