TY - GEN

T1 - Dynamically computing the maxima of decomposable functions, with applications

AU - Dobkin, David

AU - Suri, Subhash

PY - 1989

Y1 - 1989

N2 - The authors present a general technique for updating the maximum (minimum) value of a decomposable function as elements are inserted into and deleted from the set S. Applications of this technique include efficient algorithms for dynamically computing the diameter or closest pair of a set of points, minimum separation among a set of rectangles, smallest distance between a set of points and a set of hyperplanes, and largest or smallest area (perimeter) rectangles determined by a set of points. The main appeal of the approach lies in its generality. Several research directions suggested by the work are noted.

AB - The authors present a general technique for updating the maximum (minimum) value of a decomposable function as elements are inserted into and deleted from the set S. Applications of this technique include efficient algorithms for dynamically computing the diameter or closest pair of a set of points, minimum separation among a set of rectangles, smallest distance between a set of points and a set of hyperplanes, and largest or smallest area (perimeter) rectangles determined by a set of points. The main appeal of the approach lies in its generality. Several research directions suggested by the work are noted.

UR - http://www.scopus.com/inward/record.url?scp=0024768558&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024768558&partnerID=8YFLogxK

U2 - 10.1109/sfcs.1989.63523

DO - 10.1109/sfcs.1989.63523

M3 - Conference contribution

AN - SCOPUS:0024768558

SN - 0818619821

SN - 9780818619823

T3 - Annual Symposium on Foundations of Computer Science (Proceedings)

SP - 488

EP - 493

BT - Annual Symposium on Foundations of Computer Science (Proceedings)

PB - Publ by IEEE

T2 - 30th Annual Symposium on Foundations of Computer Science

Y2 - 30 October 1989 through 1 November 1989

ER -