Maintenance of Geometric Extrema ∈

David Dobkin, Subhash Suri

Research output: Contribution to journalArticle

26 Scopus citations

Abstract

Let S be a set, f: S×S→R+ a bivariate function, and f1991 the maximum value of f(x,y) over all elements y S. We say that f is decomposable with respect with the maximum if f(x,S) = max {f(x,S1),f(x,S2),…,f(x,Sk)} for any decomposition S = μi=1 i=kSi. Computing the maximum (minimum) value of a decomposable function is inherent in many problems of computational geometry and robotics. In this paper, a general technique is presented for updating the maximum (minimum) value of a decomposable function as elements are inserted into and deleted from the set S. Our result holds for a semi-online model of dynamization: When an element is inserted, we are told how long it will stay. 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) retangles determined by a set of points. These problems are fundamental to application areas such as robotics, VLSI masking, and optimization.

Original languageEnglish (US)
Pages (from-to)275-298
Number of pages24
JournalJournal of the ACM (JACM)
Volume38
Issue number2
DOIs
StatePublished - Jan 4 1991

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Keywords

  • Voronoi diagram
  • decomposability
  • dynamization
  • geometric algorithms
  • semi-online model

Fingerprint Dive into the research topics of 'Maintenance of Geometric Extrema ∈'. Together they form a unique fingerprint.

  • Cite this