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: http://www.springerlink.com/content/ph106337753883...

Related URL: http://dx.doi.org/10.1007/3-540-54967-6_80

## Abstract

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}< i_{2} and j _{1}<j_{2}, a[i_{1},j_{1}]<a[i_{1},j_{2}] implies a[i_{2},j_{1}<a[i_{2},j_{2}.) 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(n^{3/2} lg^{2}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].

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