Improved selection in totally monotone arrays

Yishay Mansour; James K. Park; Baruch Schieber; Sandeep Sen

doi:10.1007/3-540-54967-6_80

Improved selection in totally monotone arrays

Yishay Mansour, James K. Park, Baruch Schieber, Sandeep Sen

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 m × n totally monotone array. (A two-dimensional array A = {a[i,j]} is totally monotone if for all i₁ < i₂ and j₁ < j₂, a[i₁,j₁] < a[i₁, j₂] implies a[i₂, j₁] < a[i₂, j₂].) 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³/² lg² 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].

Original language	American English
Title of host publication	Foundations of Software Technology and Theoretical Computer Science - 11th Conference, Proceedings
Editors	Somenath Biswas, Kesav V. Nori
Publisher	Springer Verlag
Pages	347-359
Number of pages	13
ISBN (Print)	9783540549673
DOIs	https://doi.org/10.1007/3-540-54967-6_80
State	Published - 1991
Externally published	Yes
Event	11th Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS, 1991 - New Delhi, India Duration: Dec 17 1991 → Dec 19 1991

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	560 LNCS

Conference

Conference	11th Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS, 1991
Country/Territory	India
City	New Delhi
Period	12/17/91 → 12/19/91

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-54967-6_80

Cite this

Mansour, Y., Park, J. K., Schieber, B., & Sen, S. (1991). Improved selection in totally monotone arrays. In S. Biswas, & K. V. Nori (Eds.), Foundations of Software Technology and Theoretical Computer Science - 11th Conference, Proceedings (pp. 347-359). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 560 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-54967-6_80

Mansour, Yishay ; Park, James K. ; Schieber, Baruch et al. / Improved selection in totally monotone arrays. Foundations of Software Technology and Theoretical Computer Science - 11th Conference, Proceedings. editor / Somenath Biswas ; Kesav V. Nori. Springer Verlag, 1991. pp. 347-359 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{4a40ff1f0d854e618990c78b6fbc00c0,

title = "Improved selection in totally monotone arrays",

abstract = "This paper{\textquoteright}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].",

author = "Yishay Mansour and Park, {James K.} and Baruch Schieber and Sandeep Sen",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1991.; 11th Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS, 1991 ; Conference date: 17-12-1991 Through 19-12-1991",

year = "1991",

doi = "10.1007/3-540-54967-6_80",

language = "American English",

isbn = "9783540549673",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "347--359",

editor = "Somenath Biswas and Nori, {Kesav V.}",

booktitle = "Foundations of Software Technology and Theoretical Computer Science - 11th Conference, Proceedings",

address = "Germany",

}

Mansour, Y, Park, JK, Schieber, B & Sen, S 1991, Improved selection in totally monotone arrays. in S Biswas & KV Nori (eds), Foundations of Software Technology and Theoretical Computer Science - 11th Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 560 LNCS, Springer Verlag, pp. 347-359, 11th Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS, 1991, New Delhi, India, 12/17/91. https://doi.org/10.1007/3-540-54967-6_80

Improved selection in totally monotone arrays. / Mansour, Yishay; Park, James K.; Schieber, Baruch et al.
Foundations of Software Technology and Theoretical Computer Science - 11th Conference, Proceedings. ed. / Somenath Biswas; Kesav V. Nori. Springer Verlag, 1991. p. 347-359 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 560 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

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

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 -

Mansour Y, Park JK, Schieber B, Sen S. Improved selection in totally monotone arrays. In Biswas S, Nori KV, editors, Foundations of Software Technology and Theoretical Computer Science - 11th Conference, Proceedings. Springer Verlag. 1991. p. 347-359. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-54967-6_80

Improved selection in totally monotone arrays

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this