2008/04/06 by Mark de Berg, de Berg, Mark, Shripad Thite +1
Computer Science · Engineering · #Algorithms and Data Compression #Optimization and Search Problems #cs.DS #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.0804.0936
arxiv created 2008/04/06 · arxiv updated 2009/12/01
Let X[0..n-1] and Y[0..m-1] be two sorted arrays, and define the mxn matrix A by A[j][i]=X[i]+Y[j]. Frederickson and Johnson gave an efficient algorithm for selecting the k-th smallest element from A. We show how to make this algorithm IO-efficient. Our cache-oblivious algorithm performs O((m+n)/B) IOs, where B is the block size of memory transfers.