In:
International Journal of Computational Geometry & Applications, World Scientific Pub Co Pte Ltd, Vol. 03, No. 02 ( 1993-06), p. 115-132
Abstract:
This paper's main result is an [Formula: see text]-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 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. An immediate consequence of this result is an O(n 3 / 2 lg 1/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⌉ − 1.
Type of Medium:
Online Resource
ISSN:
0218-1959
,
1793-6357
DOI:
10.1142/S0218195993000087
Language:
English
Publisher:
World Scientific Pub Co Pte Ltd
Publication Date:
1993
SSG:
11
Permalink
