Selection on \(X_1 + X_1 + \cdots X_m\) via Cartesian product tree

Selection on the Cartesian product is a classic problem in computer science. Recently, an optimal algorithm for selection on \(X+Y\), based on soft heaps, was introduced. By combining this approach with layer-ordered heaps (LOHs), an algorithm using a balanced binary tree of \(X+Y\) selections was p...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-08
Main Authors: Kreitzberg, Patrick, Lucke, Kyle, Pennington, Jake, Serang, Oliver
Format: Article
Language:English
Subjects:
Algorithms
Cartesian coordinates
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Selection on the Cartesian product is a classic problem in computer science. Recently, an optimal algorithm for selection on \(X+Y\), based on soft heaps, was introduced. By combining this approach with layer-ordered heaps (LOHs), an algorithm using a balanced binary tree of \(X+Y\) selections was proposed to perform \(k\)-selection on \(X_1+X_2+\cdots+X_m\) in \(o(n\cdot m + k\cdot m)\), where \(X_i\) have length \(n\). Here, that \(o(n\cdot m + k\cdot m)\) algorithm is combined with a novel, optimal LOH-based algorithm for selection on \(X+Y\) (without a soft heap). Performance of algorithms for selection on \(X_1+X_2+\cdots+X_m\) are compared empirically, demonstrating the benefit of the algorithm proposed here.
ISSN:2331-8422