{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T15:41:07Z","timestamp":1648741267577},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[1993,6]]},"abstract":"<jats:p> This paper's main result is an [Formula: see text]-time algorithm for computing the kth smallest entry in each row of an m\u00d7n totally monotone array. (A two-dimensional array A={a[i, j]} is totally monotone if for all i<jats:sub>1<\/jats:sub>&lt;i<jats:sub>2<\/jats:sub> and j<jats:sub>1<\/jats:sub>&lt;j<jats:sub>2<\/jats:sub>, a[i<jats:sub>1<\/jats:sub>, j<jats:sub>1<\/jats:sub>]&lt;a[i<jats:sub>1<\/jats:sub>, j<jats:sub>2<\/jats:sub>] implies a[i<jats:sub>2<\/jats:sub>, j<jats:sub>1<\/jats:sub>]&lt;a[i<jats:sub>2<\/jats:sub>, j<jats:sub>2<\/jats:sub>].) For large values of k (in particular, for k=\u2308n\/2\u2309), 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<jats:sup>3<\/jats:sup>\/<jats:sup>2<\/jats:sup> lg <jats:sup>1\/2<\/jats:sup> 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\u00d7n totally monotone array; this approximate median is an entry whose rank in its row lies between \u230an\/4\u230b and \u23083n\/4\u2309 \u2212 1. <\/jats:p>","DOI":"10.1142\/s0218195993000087","type":"journal-article","created":{"date-parts":[[2004,11,22]],"date-time":"2004-11-22T22:29:30Z","timestamp":1101162570000},"page":"115-132","source":"Crossref","is-referenced-by-count":3,"title":["IMPROVED SELECTION IN TOTALLY MONOTONE ARRAYS"],"prefix":"10.1142","volume":"03","author":[{"given":"YISHAY","family":"MANSOUR","sequence":"first","affiliation":[{"name":"T. J. Watson Research Center, IBM Research Division, P. O. Box 704, Yorktown Heights, NY 10598, U.S.A."}]},{"given":"JAMES K.","family":"PARK","sequence":"additional","affiliation":[{"name":"Org. 1423, Sandia National Laboratories, P. O. Box 5800, Albuquerque, NM 87185, U.S.A."}]},{"given":"BARUCH","family":"SCHIEBER","sequence":"additional","affiliation":[{"name":"T. J. Watson Research Center, IBM Research Division, P. O. Box 218, Yorktown Heights, NY 10598, U.S.A."}]},{"given":"SANDEEP","family":"SEN","sequence":"additional","affiliation":[{"name":"Dept. of Computer Science and Engineering, Indian Institute of Technology, Delhi, Hauz Khas, New Delhi 110016, India"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195993000087","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T19:57:39Z","timestamp":1565121459000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195993000087"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,6]]},"references-count":0,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1993,6]]}},"alternative-id":["10.1142\/S0218195993000087"],"URL":"https:\/\/doi.org\/10.1142\/s0218195993000087","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,6]]}}}