Improved selection in totally monotone arrays

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

Research output: Chapter in Book/Report/Conference proceedingConference 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 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].

Original languageEnglish (US)
Title of host publicationFoundations of Software Technology and Theoretical Computer Science - 11th Conference, Proceedings
EditorsSomenath Biswas, Kesav V. Nori
PublisherSpringer Verlag
Pages347-359
Number of pages13
ISBN (Print)9783540549673
DOIs
StatePublished - 1991
Externally publishedYes
Event11th Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS, 1991 - New Delhi, India
Duration: Dec 17 1991Dec 19 1991

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume560 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference11th Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS, 1991
Country/TerritoryIndia
CityNew Delhi
Period12/17/9112/19/91

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Improved selection in totally monotone arrays'. Together they form a unique fingerprint.

Cite this