Access Restriction

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

   Open content in new tab
Source: ACM Digital Library