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 -