Dynamically computing the maxima of decomposable functions, with applications

David Dobkin, Subhash Suri

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherPubl by IEEE
Pages488-493
Number of pages6
ISBN (Print)0818619821
StatePublished - Nov 1 1989
Event30th Annual Symposium on Foundations of Computer Science - Research Triangle Park, NC, USA
Duration: Oct 30 1989Nov 1 1989

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

Other

Other30th Annual Symposium on Foundations of Computer Science
CityResearch Triangle Park, NC, USA
Period10/30/8911/1/89

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Dynamically computing the maxima of decomposable functions, with applications'. Together they form a unique fingerprint.

Cite this