### Maintenance of geometric extrema ∈Maintenance of geometric extrema ∈

Access Restriction
Subscribed

 Author Dobkin, David ♦ Suri, Subhash Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1991 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Voronoi diagram ♦ Decomposability ♦ Dynamization ♦ Geometric algorithms ♦ Semi-online model Abstract Let $\textit{S}$ be a set, $\textit{f}:$ $\textit{S}×\textit{S}→\textit{R}+$ a bivariate function, and $\textit{f}(\textit{x},\textit{S})$ the $\textit{maximum}$ value of $\textit{f}(\textit{x},\textit{y})$ over all elements $\textit{y}∈\textit{S}.$ We say that $\textit{f}$ is $\textit{decomposable}$ with respect with the maximum if $\textit{f}(\textit{x},\textit{S})$ = max ${\textit{f}(\textit{x},\textit{S}1),\textit{f}(\textit{x},\textit{S}2),…,\textit{f}(\textit{x},\textit{Sk})}$ for any decomposition $\textit{S}$ = $μ\textit{i}=1\textit{i}=\textit{k}\textit{Si}.$ 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 $\textit{S}.$ Our result holds for a $\textit{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 $\textit{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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1991-04-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 38 Issue Number 2 Page Count 24 Starting Page 275 Ending Page 298

#### Open content in new tab

Source: ACM Digital Library