TY - GEN

T1 - Improved selection in totally monotone arrays

AU - Mansour, Yishay

AU - Park, James K.

AU - Schieber, Baruch

AU - Sen, Sandeep

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1991.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 1991

Y1 - 1991

N2 - 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 m × n totally monotone array. (A two-dimensional array A = {a[i,j]} is totally monotone if for all i1 < i2 and j1 < 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 lg2 n)-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].

AB - 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 m × n totally monotone array. (A two-dimensional array A = {a[i,j]} is totally monotone if for all i1 < i2 and j1 < 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 lg2 n)-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].

UR - http://www.scopus.com/inward/record.url?scp=85030634168&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85030634168&partnerID=8YFLogxK

U2 - 10.1007/3-540-54967-6_80

DO - 10.1007/3-540-54967-6_80

M3 - Conference contribution

AN - SCOPUS:85030634168

SN - 9783540549673

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 347

EP - 359

BT - Foundations of Software Technology and Theoretical Computer Science - 11th Conference, Proceedings

A2 - Biswas, Somenath

A2 - Nori, Kesav V.

PB - Springer Verlag

T2 - 11th Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS, 1991

Y2 - 17 December 1991 through 19 December 1991

ER -