Improved selection in totally monotone arrays

Mansour, Yishay ; Park, James K. ; Schieber, Baruch ; Sen, Sandeep (1991) Improved selection in totally monotone arrays Foundations of software technology and theoretical computer science : 11th conference, 560 . pp. 347-359. ISSN 0302-9743

Full text not available from this repository.

Official URL:

Related URL:


This paper's main result is an O((√m lg m)(n lg n)+m lg n)-time algorithm for computing the kth smallest entry in each row of an mxn totally monotone array. (A two-dimensional array A = {a[i,j]} is totally monotone if for all i 1< i2 and j 1<j2, a[i1,j1]<a[i1,j2] implies a[i2,j1<a[i2,j2.) For large values of k (in particular, for k=[n/2]), this algorithm is significantly faster than the O(k(m+n))-time algorithm for the same problem due to Kravets and Park (1991). An immediate consequence of this result is an O(n3/2 lg2n)-time algorithm for computing the kth nearest neighbor of each vertex of a convex n-gon. In addition to the main result, we also give an O(n lg m)-time algorithm for computing an approximate median in each row of an m× n totally monotone array; this approximate median is an entry whose rank in its row lies between [n/4] and [3n/4].

Item Type:Article
Source:Copyright of this article belongs to Springer.
ID Code:90073
Deposited On:04 May 2012 14:27
Last Modified:04 May 2012 14:27

Repository Staff Only: item control page