\documentclass[a4paper,11pt]{article}
\usepackage{latexsym,psfig}
\author{Adli Abu Shaban}
\title{Dynamic Algorithms}
\frenchspacing
\begin{document}
\maketitle
\tableofcontents
\pagebreak
\section{Introduction}

If we are interested in keeping track of the update that happens to a Geometric 
complex like trapezoidal decomposition, semidynamic algorithms are algorithms that keep track of addition of segments 
into a set of segments $M$. Dynamic algorithms will keep track of
addition as well as deletion of segments. In dynamic algorithms, our goal is 
to maintain a geometric complex $H(M)$. So whenever the user adds or 
deletes a segment from $M$, we want to update $H(M)$ quickly.

To evaluate dynamic algorithm, the best one can hope for is that it 
performs an update in time proportional to the structural change in the 
underlying geometric complex $H(N)$.
\subsection{Notations and definitions}
Consider when deletion is allowed in an update sequence $\bar u$. The signature of the update
 sequence is $\delta = \delta(\bar u)$.
Its signature $\delta = \delta(u)$ is the string of + and - symbols
such that the $i$th symbol in $\delta(u)$ is + iff the $i$th update in u is addition. 
Let $N$ be the set of segments or objects involved in $\bar u$. The size of $N$
is referred to by $n$.

Not every sequence $\delta$ of + and - symbols can occur as a signature of an 
update sequence. Consider $r(\delta, i)$, the rank of $\delta$ at time $i$,
to be the number of +'s minus the number of -'s in an update sequence. If $\delta$ is the signature of an 
update sequence $\bar u$, then $r(\delta, i)$
can only denote the number of current objects at time $i$. Then $\delta$ is a valid signature for all 
$i$ iff $r(\delta, i)$ $\geq 0$. So $r(\delta, i)$ can be denoted by just $r(\delta)$. When the update 
sequence involves addition only, $\delta$ = $+^\mathrm{n}$ and $r(+^\mathrm{n}, i) =i$ .\textbf{Weakly monotonic} 
signature, $\delta$, happens if $r(i)$ = $\Omega(i)$. This is equivalent to saying that there exists a constant $b 
\geq$ 1 such that $r(i) \geq {i \over b}$. In other words, there exists a few deletions in the update sequence. 
The more deletions in the update sequence, the more the signature gets away from weakly 
monotonic to nonmontonic.

\begin{figure}[htbp]
        \hspace{1.1in}
        \psfig{figure=figure1.ps}
        \caption{Figure 1:Examples of signatures
                }
        \label{cubes}
\end{figure}

\subsection{Random update sequence}
An update sequence is random if it is chosen from a uniform distribution on all valid sequences. Let $|\bar u|$ denote
the length of $\bar u$. For each $i \leq  |\bar u|$ let $S^\mathrm{i}$ denote the object in the $i$th update. 
Let $N^\mathrm{i}$ denote the set of undeleted objects existing at time i during the execution of $|\bar u|$. 
If the update sequence, $(N, \delta)$-sequence, is random then each object in $N$ is equally likely to 
be $S^\mathrm{i}$ and $N^\mathrm{i}$ is a random subset of $N$ of size $r(i)$. 

\section{Trapezoidal decomposition}
Consider $N^\mathrm{k}$ to be the set of undeleted segments of a trapezoidal decomposition existing at time $k$. 
Let $H(N^\mathrm{k})$ denote the resulting trapezoidal decomposition.
Our goal is to maintain $H(N^\mathrm{k})$. Let $S$ = $\mathnormal{S_k}+1$ be the segment involved in
the $(k+1)$th update. Our goal is to update $H(N^\mathrm{k})$ to $H(N^\mathrm{k+1})$ quickly.

	
\textbf{Addition}: Here, the ($k+1$)th update is an addition of S to $N^\mathrm{k}$. If we assume that the 
trapezoid in $H(N^\mathrm{k})$ containing an endpoint of $S$, we can add $S$ to $H(N^\mathrm{k})$ as 
the semidynamic algorithm. The point location issue will be discussed later.

	
\textbf{Deletion}: The $(k+1)th$ update is the deletion of segment $S$ from $N^\mathrm{k}$. First the 
segment $S$ is made transparent to all vertical attachments adjacent to it. Those vertical attachments 
are made to pass through $S$ because segment $S$ does not exist to them any more. Here we obtain a 
temporary partition, $\hat{H}(N^\mathrm{k})$. The final partition, $N^\mathrm{k+1}$ can be obtained 
from $\hat{H}(N^\mathrm{k})$ by erasing the segment $S$. The whole update can be done in time proportional 
to $\sum_f$ face-length(f), where $f$ ranges over all trapezoids in $H(N^\mathrm{k})$ adjacent to $S$.
\begin{figure}[htbp]
        \hspace{1.1in}
        \psfig{figure=figure2.ps}
        \caption{Figure 2:Trapezoidal Decomposition update}
        \label{cubes}
\end{figure}
\textbf{Analysis}

\textbf{First case}, when the $(k+1)$th update is \textit{addition} of $S$ to $N^\mathrm{k}$. The cost of 
endpoint location in segment $S$ will be ignored here. The excepted cost, conditional on a fixed $N^\mathrm{k+1}$, 
is proportional to
\begin{displaymath}
\frac{|H(N^\mathrm{k+1})|}{|N^\mathrm{k+1}|}
= O \left(\frac{|N^\mathrm{k+1}| + I_k+1}{|N^\mathrm{k+1}|} \right) =
O \left (1+\frac{I_k+1}{r(k+1)}\right),
\end{displaymath}
where $I_{k+1}$ is the number intersection among the segment in $N^\mathrm{k+1}$.

\textbf{Second case}, consider the case when the $(k+1)$th update involves \textit{deletion} of segment $S$ from
 $N^\mathrm{k}$. The expected cost, conditional on fixed $N^\mathrm{k}$, is proportional to
\begin{displaymath}
\frac{|H(N^\mathrm{k})|}{|N^\mathrm{k}|} = O\left(\frac{|N^\mathrm{k}|+I_k}{|N^\mathrm{k}|}\right) = O\left(1+\frac{I_k+1}{r(k+1)}\right),
\end{displaymath}
where $I_{k}$ is the number intersection among the segment in $N^\mathrm{k}$.

Now, we are going to calculate the expected cost of the algorithm over a random $(N, \delta)$-sequence. 
In the random sequence, $N^\mathrm{k}$ is a random subset of $N$ of size $r(k)$. 
The expected value of $I_k$ is $O(r(k)^\mathrm{2}I/n^\mathrm{2})$, where $I$ is the number of intersection 
among the segments in $N$. So the expected total cost is bounded	within a constant factor by,
\begin{displaymath}
\sum_{k=1}^{|\bar u|}1+\frac{r(k)I}{n^\mathrm{2}}=n+\frac{I}{n^\mathrm{2}}\sum_{k=1}^{|\bar u|}r(k)=O(n+I)
\end{displaymath}
To summarize, the expected cost of maintaining a trapezoidal decomposition over a random sequence, ignoring the endpoint location, is in the order of 
\begin{displaymath}
n+\frac{I}{n^\mathrm{2}}\sum_{i=1}^{|\bar u|}r(k)=O(n+1),
\end{displaymath}
where $I$ is the number of intersections among the segments in $N$.

\subsection{Point location}
In the previous analysis, we ignored the cost of locating the endpoint in the updated segment. 
Lets consider a sequence of $(N, \delta)$, $\bar u$. Let $N^\mathrm{k}$ be the set of undeleted segments existing at time $k$. Here we introduce history($k$). The history($k$) will point to the trapezoids in $H(N^\mathrm{k})$. Therefore, history(0) consists of one node that corresponds to whole plane. Inductively, assume that history($k$) has been defined. Now, consider the $(k+1)$th update of segment $S_{k+1}$. History($k+1$) is obtained from history($k$) as follows:
\begin{enumerate}
\item Mark the leaves of history($k$) corresponding to the trapezoids in the $H(N^\mathrm{k})$ that are destroyed during the $(k+1)th$ update as killed.
\item Allocate new nodes for the newly created trapezoids in $H(N^\mathrm{k+1})$.
\item Build a certain data structure link($S_{k+1}$), which serves as a link between the decomposition $H(N^\mathrm{k})$. 
\end{enumerate}

If the $(k+1)th$ update is addition, every destroyed trapezoids in $H(N^\mathrm{k})$ has at most four children. Link($S_{k+1}$) consists of pointers from the killed leaves of history($k$) to their children. 

If the ($k+1$)th update is deletion, the number of destroyed children need not be bounded by any number. 
The children of any killed trapezoids can be ordered from left to right. We let the link($S_{k+1}$) 
consist of linearly ordered list of children, one list for each killed leaf of history($k$). 
With each such linearly ordered list, we maintain a search tree. Given any point $p$ lying 
within a killed trapezoid in $H(N^\mathrm{k})$, link($S_{k+1}$), allows us to locate its 
child containing $p$ in $O(log|N^\mathrm{k}|) = O(\log{r}(k))$ time.

Let $p$ be a fixed query point. To locate $p$ in $H(N^\mathrm{k})$, we begin at the root of 
history($k$), which corresponds to the whole plane. We descend to its unique child containing 
$p$ and keep repeating this process until we reach a leaf of history($k$). This leaf corresponds 
to the trapezoid in $H(N^\mathrm{k})$ containing $p$. Each descent takes at most logarithmic time. 
The cost of locating a point would be proportional to the length of the search path in history($k$), ignoring a logarithmic factor.

\textbf{Analysis of end point location}
Given $j\leq{k}$, we define a 0-1 random variable $V_j$. $V_j$ is defined to be 1 if the trapezoid in 
$H(N^\mathrm{j-1})$ containing the query point $p$ is destroyed during the $j$th update. Otherwise, it 
is defined to be 0. Here we find out that the expected length of the search path is of the order of 
$\sum_{j=1}^{|\bar u|}\frac{1}{r(j)}$

If the signature is weakly monotonic signature, where $r(j)=\Omega(j)$, the expected length of the search path $O(\log{k})$. This is the case for most update sequences but the worst case is $O(k)$.\\
\textbf{Theorem} The expected cost of maintaining a trapezoidal decomposition and the history over a random sequence id of the order of 
\begin{equation}
n+\frac{I}{n^\mathrm{2}}\sum_{i=1}^{|\bar u|}r(k) = O(n+I),
\end{equation}
where I is the number of intersections among the segments in $N$. This ignores the cost of point location during addition. the expected cost of point location at time k is $O(\log{k}\sum_{j\leq{k}}1/r(j))$ If $\delta$ is weakly monotonic, it is $O(log^\mathrm{2}k)$ for most sequences.

Therefore, the performance for this algorithm is not satisfactory if $\delta$ is not weakly monotonic. Since the history can become long and dirty if it contains too many segments that have already been deleted. 

\section{Voronoi diagrams}
Let $N^\mathrm{k}$ denote the set of undeleted sites existing at time $k$. Let $G(N^\mathrm{k})$ denote their Voronoi diagram. The goal is to maintain $G(N^\mathrm{k})$.
So if we have an update, $(k+1)$th, and a segment, $S=S_{k+1}$ to be the site involved in the update. The goal is to update $G(N^\mathrm{k})$ to $G(N^\mathrm{k+1})$ very quickly.

\textbf{Update}
Lets consider when the update is deletion of segment $S$ from $N^\mathrm{k}$. Let $Q_1$, $Q_2$, $Q_3$, 
...$Q_j$ be the sites labeling the regions adjacent to the Voronoi region we want to delete, vor($S$). 
The Voronoi diagram of $N^\mathrm{k+1}$ can be obtained from Voronoi diagram as follows
\begin{enumerate}
\item Separately compute the Voronoi diagram of the sites $Q_1$, $Q_2$, $Q_3$, ...$Q_j$, which can be 
done in $O(j\log{j})$. This decomposes the vor($S$) into $O(j)$ convex regions.
\item Remove the $j$ edges bounding vor($S$).
\end{enumerate}
The result will be the Voronoi diagram of $N^\mathrm{k+1}$. The structural 
change in the Voronoi diagram, as the update happen, is proportional to $j$ and 
ignoring a logarithmic factor. The structural change is the number of newly 
created and destroyed edges and veracities.
\begin{figure}[htbp]
        \hspace{1.1in}
        \psfig{figure=figure3.ps}
        \caption{Figure 3: Vorornoi Diagrams update}
        \label{cubes}
\end{figure}
\textbf{Analysis}
We have seen that the structural change during the deletion of site $S\in N^\mathrm{k}$ is $O(j)$. 
Where $j$ is the size of $vor(S)$ which is 
proportional to the number of vertices in $G(N^\mathrm{k})$ that are destroyed 
during deletion.  A vertex $v$ is destroyed during deletion iff the deleted site is one 
of the three sites defining $v$. Summing up the structural change by 
letting the deleted site $S^\mathrm{k+1}$ range all over all sites in 
$N^\mathrm{k}$. It follows that the sum, $\phi$, is proportional to the size of 
$G(N\mathrm{k})$. Since the size of planar Voronoi diagram is linear in the 
number of sites, then the sum, $\phi$, of structural change is 
$(|N^\mathrm{k}|)$. Since the deleted site $S_{k+1}$ is randomly chosen from 
$N^\mathrm{k}$, the expected structural change is $\phi/|N^\mathrm{k}|= O(1)$. 
If the update is addition, we use the backward analysis. We find that the 
expected structural change during each update in a random $(N, \delta)$-sequence 
is $O(1)$. Therefor, the total expected structural change is $O(n)$.
\subsection{Conflict search}
Conflict search, here, means locating the conflicting vertex during the addition of new site.
We use the history technique to help us the conflicting vertices.
\begin{enumerate}
\item Mark the leaves of history($k$) pointing to the destroyed vertices in 
$G(N^\mathrm{k})$ as killed.
\item Locate new nodes for the newly created vertices of $G(N^\mathrm{k+1})$.
\item Link the killed and the newly created nodes according to their adjacencies.
\end{enumerate}
Suppose we know a leaf of history($k$) in conflict with the updated site, $I$. 
We descend to a leaf of history($k+1$) in conflict with $I$ as follows. The 
killed and the newly created nodes of link($S_{k+1}$) in conflict with $I$ form 
its connected subgraph. We start the search at the known conflicting leaf of 
history($k$) and restrict the search to the above connected subgraph of 
link($S_{k+1}$). We stop the search as soon as we reach a newly created node in 
conflict with $I$. In the worst case, the cost of the search is proportional to 
the size of the connected subgraph.\\
\textbf{Using history in conflict search}
\begin{enumerate}
\item Locate a node of histroy(1) in conflict with $S$. This takes $O(1)$ time. 
\item Assume that this node is killed at time $j$.
\item Using link($S_j$), locate a node created at time $j$ in conflict with $S$.
\item Repeat this process until we reach a leaf of history($k$). This will correspond to a vertex 
of $G(N^\mathrm{k})$ in conflict with $S$.
\end{enumerate}
In the worst case, the cost of this conflict search is proportional to the total 
number of nodes in history($k$) in conflict with $S$.

\textbf{Analysis}
If the update sequence under consideration is random, the expected number of nodes 
in history($k$) in conflict with $S_{k+1}$ is $O(\log{k})$. This assumes that the signature is weakly monotonic.
\\
Assuming that $\delta$ is weakly monotonic, the expected cost of maintaining a Voronoi 
diagram over a random sequence is $O(n \log{n})$. The expected cost of conflict search 
through history($k$) during the addition of $S_{k+1}$ is $O(\log{k})$.
\section{History and configuration spaces}
In this section, I will briefly go over the notations and the analysis because I think that all 
information presented in this section are repetitive from previous sections.
Consider dynamically maintaining a geometric complex $H(M)$. Let $\bar u$ be any sequence. 
The history at time $k$ during the execution of $\bar u$ is data structure that results by 
remembering the differences between the successive partitions in the sequence. The leaves 
of history($k$) correspond to the faces of  $H(N^\mathrm{k})$ of all or some specified dimensions. 
It is assumed that these faces are configurations that are defined by abounded number of objects in $N^\mathrm{k}$.
\subsection{Expected performance}
The total number of nodes in the history of  $\bar u$ is bounded by the total structural 
change during $\bar u$. Let $\Pi^{0}(N^\mathrm{k})$ be the set of active configurations at time $k$. 
 We want to get the number of configurations in $\Pi^{0}(N^\mathrm{i})$ that are destroyed 
during update. First calculate the expected value, conditional on a fixed $N^\mathrm{i}$. 
A configuration $\sigma \in \Pi^{0}(N^\mathrm{i})$ can be destroyed iff the deleted objects 
is one of the most $d$ triggers associated with $\sigma$.  If we sum the number of destroyed 
configurations by letting the deleted object $S$ ranges over all of $N^\mathrm{k}$, then the 
sum is at most $d\pi^{0}(N^\mathrm{i})$.  Where the size of  $\Pi^{0}(N^\mathrm{i})$ 
is $\pi^{0}(N^\mathrm{i})$. Each object in $N^\mathrm{i}$ is equally likely to be deleted. 
Then the expected number of destroyed configurations in $\Pi^{0}(N^\mathrm{i})$, conditional on a fixed $N^\mathrm{i}$ is at most 
\begin{displaymath}
d\pi^{0}(N^\mathrm{i})/|N^\mathrm{i}| = d\pi^{0}(N^\mathrm{i})/r(i).
\end{displaymath}
The expected number of newly created configurations, conditional on a fixed $N^\mathrm{i}$, is  
\begin{displaymath}
\pi^{1}(N^\mathrm{i})/(|N^\mathrm{i}|) = \pi^{1}(N^\mathrm{i})/r(i).
\end{displaymath}
Now lets assume that $N^\mathrm{i}$ is arandom sample of $N$ of size $r(i)$. For $c\geq{0}$, 
let $e^\mathrm{c}(r)$ denote the expected value of  $\pi^\mathrm{c}(R)$, where R is a random 
sample of $N$ of size $r$. Here $\pi^\mathrm{c}$ is the size of $\Pi^\mathrm{c}(R)$, 
the set of configurations in $\Pi(R)$ with level $c$. Note that $e^\mathrm{0}(r)$ is just $e(r)$.
The expected structural changes during the ($i$ +1)th update of a random sequence, assuming that it is deletion is bounded by
\begin{displaymath}
\frac{d e(r(i))+e^{1}(r(i))}{r(i)}.
\end{displaymath}
The expected structural change, conditional on a fixed $N^\mathrm{i+1}$ is bounded by
\begin{displaymath}
\frac{d e(r(I+`)) + e^{1}(r(i+1))}{r(i+1i)}.
\end{displaymath}
The expected value of the total structural change during a random sequence is
\begin{displaymath}
\sum_{k=1}^{|\bar u|}\frac{d c(r(k))+e^{1}(r(k))}{r(k)}.
\end{displaymath}
Here $d$ is the maximum degree of a configuration in $\Pi(N)$.
Let $a>0$ be a fixed integer. Consider any configuration space $\Pi(R)$. Let $d$ be 
the maximum degree of a configuration in $\Pi(R)$. Let $r$ be the size of $R$. Let $Q$ be a random sample of $R$ of size $r/2$. Then
\begin{displaymath}
\pi^{a}(R)=O(2^{a+d}E[\pi^{0}(Q)]).
\end{displaymath}
The probability that any given element in $R$ occurs in $Q$ is 1/2. It follows that 
\begin{displaymath}
prob(\sigma \in \Pi^{0}(Q))\approx\frac{1}{2^{d(\sigma)+a}},
\end{displaymath}
where $\approx$ denotes asymptotic equality with a constant factor ignored. 
This equation is exact if $Q$ is chosen by flipping a fair coin. If $Q$ is a 
random subset of size exactly $r$/2, then one can calculate the exact expression in termsof binomial coefficients.
The expected structural change during a random a sequence is bounded, within a constant factor, by
\begin{displaymath}
\sum_{k=1}^{|\bar u|}\frac{e(r(k))+e(r(k)/2)}{r(k)}=O\left(\sum_{k}\frac{\bar e(r(k))}{r(k)}\right).
\end{displaymath}
If $\Pi(N)$ is trvial configuration space then the expected structural change during a 
random sequence is $O(\sum_k 1/r(k))$. In particular, it is $O(\log{n}$ if $\delta$ is
 weakly monotonic. For most update sequences, the bound is $O(\log{n})$.
Lets consider a random sequence. Suppose the ($k$+1)th update during this sequence is 
addition of $S_{k+1}$. Within a constant factor, by $\sum_{i\leq{k}}\bar{e}(r(I))/r(i)^2$.
 In particular, this is of the order of $\sum_{I\leq{k}}\bar{e}(i)/i^2$, if $\delta$ is 
weakly monotonic.
\section{Rebuilding history}
The performance of the previous history-based algorithm is not satisfactory 
enough if the signature of the update sequence is not weakly monotonic. The 
source of this problem is that history($k$) can depend on several dead objects 
in the past whose number can exceed the number of active objects at time $k$.
An object occurring in history($k$) is called dead if the deletion of that 
object has already occurred in the update sequence $\bar u$.
\begin{figure}[htbp]
        \hspace{1.1in}
        \psfig{figure=figure4.ps}
        \caption{Figure 4: History rebuilding}
        \label{cubes}
\end{figure}
Rebuilding history works as follow; every time the number of dead objects 
in the history exceeds, say, twice the number of active objects in the history,
we rebuild history from scratch. 

Rebuilding is done just by adding the
currently active objects in the same order in which they where added previously,
although it might be better to add them in random order. The resulting history
is as if the dead objects were never encountered during the previous updates. 
We keep rebuilding history in this fashion whenever required.
We want to know the cost of rebuilding. Rebuilding works by adding the 
currently active objects in the same order they were added originally. 
The number of these objects is clearly less than the number of dead objects. 
We could see that the total number of additions during all rebuildings is 
less than the length of $\bar u$.
If  $a(l)$ denote the number of active objects at the time of the $l$th 
rebuilding, then $\sum_{l}a(l)\leq|\bar u^2|$.
For example, consider the dynamic maintenance of Voronoi diagrams. The $l$th rebuilding 
involves $a(l)$ additions of sites. The cost of rebuilding is expected to be $O(a(l)\log{a})$.\\
\textbf{Theorem} The expected cost of maintaining a planar Voronoi diagram over a random sequence is $O(n\log{n})$.

For trapezoidal decomposition, let $I(l)$ denote the number of intersections among the 
$a(l)$ segments that are added during the $l$th rebuilding. The expected cost of the $l$th 
rebuilding is $O(I(l)+a(l))$ for semidynamic case. The expected value of $I(l)$ is
 $O(a(l)^{2}I/n^{2})$, where $I$ is the number of intersections among the segments in $N$ . \\
\textbf{Theorem} The expected cost of maintaining a trapezoidal decomposition over a 
random sequence is $O(n\log{n}+I)$.
\section{Deletions in history}
History rebuilding works by removing dead objects periodically. Here we 
introduce a new technique. We want to minimize the number of dead objects 
at any time. With this method, the number of dead objects is 0. 

Deletion in history works by deleting the object from history whenever 
we encounter a delete operation. Once this is done, the history should 
look as if the deleted objects where never added in the first place. 
Let $M$ be the set of active objects at any given time. The size of
$M$ is denoted by $m$. Let $M^\mathrm{j}$ be the set of first $j$ objects. 

The history associated with $M$ is denoted by history($M$). 
Deletion from history($M$) can be done through a series of operations 
called \textbf{rotations}. Let $S\in M$ be the object we want to delete 
from history($M$). Let $M'$ denote the set $M\setminus{S}$, with naturally 
inherited order. The goal is to obtain history($M'$) from history($M$). 
Deletion of $S$ from history($M$) is carried out as follows.
\begin{enumerate}
\item Let $l$ be the number of objects in $M$ with order higher than $S$
\item For $I \leq{l}$ define $M(i)$ to be the ordered set obtained from $M$ by moving $S$ higher in order by $i$ places.
\item We obtain history($M'$) from history($M$) by moving $S$ higher in order step by step until it has the highest order.
\item Deleting $S$ is easy, then.
\end{enumerate}
This approach has one problem, it always needs $l$ distinct rotations. This implies 
as $\Omega(l)$ lower bound on the cost of deletion.  We can get around this difficulty 
as follows. Let $S'$ be the object just higher than $S$ in order on $B$. Let $C=M(i+1)$ 
be the order obtained by switching the orders of $S$ and $S'$ in $B$. So $S$ and $S'$ 
commute if history($B$) and history($C$) are identical. Begin with history($M$). 
Let ($S'$) be the first object commuting with $S$ with higher order than $S$. 
Rotate $S$ and $S'$ and keep on repeating this process until there is no noncommuting 
object with higher order than $S$. At this point perform the deletion.
\textit{How do we know $S'$?}. Let $S$ and $S'$ be any two objects in $B$ such that $S$ 
immediately precedes $S'$ in the order. Let $C=B(S, S')$ be the order obtained from $B$ by witching the orders of $S$ and $S'$.
Commutativity Condition: History($B$) and history($C$) are identical data structures 
if no descendent of $S$ in history($B$) is killed by $S'$. 

The deletion algorithm can be further refined as follows. Suppose we want to 
delete an object $S$ from history($M$). Let $\Gamma$ be the set of descendents of 
$S$ in history($M$).  Let killer($\Gamma$) be the priority queue of the killers of the nodes in $\Gamma$.\\
\textbf{General Deletion Algorithm} 
\begin{enumerate}
\item Remove the first object $S'$ in killer($\Gamma$). By the commutativiity condition, 
$S$ commutes with all objects in $M$, whose current ranks lie between $S$ and $S'$. 
\item Let $\Gamma(S')$ be the subset of  $\Gamma$ killed by $S'$. The subset $\Gamma(S')$ 
is available now. Usign this information, switch the orders of  $S$ and $S'$ in $M$. Update history($M$) via rotation.
\item Replace the subset $\Gamma(S')$ of $\Gamma$ by the new descendents of $S$ in history($M$) and 
update the priority queue killer($\Gamma$).
\item If killer($\Gamma$) is not empty, go to step 1.
\item End deletion: Now the order of $S$ in $M$ can be assumed to be the highest. 
Remove link($S$) and the descendents of $S$ in history($M$).
\end{enumerate}
\textbf{Analysis}
The cost of this deletion algorithm is controlled by the structural change. This is defined 
as the sum of the structural changes during all rotations. Its expected value is bounded in the following theorem.\\
\textbf{Theorem} Let $e( i, M$) denote the expected size of $\Pi^0(B)$, where $B$ is a random 
sample $M$ of size $i$. Suppose the ordering of the objects in $M$ is random. Then the total 
number expected structural change during a deletion of random object from history($M$) is 
bounded within a constant factor, by $\frac{1}{m}\sum_{i=1}^{m}e(i, M)/i$. 
The sum $\sum_{i=1}^{m}e(i, M)/i$ is the expected size of history($M$). What the theorem 
is saying is that the average structural change during a random deletion from $M$ is approximately 
$(1/{m})$th fraction of the expected size of history.
\subsection{Convex polytopes}
Let $M$ denote the set of undeleted half-spaces existing at any given time. Let $H(M)$ denote the 
convex polytope formed by intersecting these half-spaces.
Suppose we want to delete a half-space $S\in{M}$. This will be done by applying the general 
deletion scheme. First we bring $S$ to the end of ordering on $M$ via rotations and then perform deletion.
 
Let $A$ be any ordered set of half-spaces. Let $R$ and $R'$ be any two consecutive half-spaces 
in the ordering on $A$. Assume that they do not commute. Let $\bar A$ be the order obtained 
from $A$ by switching the orders of $R$ and $R'$. Update the history($A$) to history($\bar A$) as follows;
\begin{enumerate}
\item let $j$ be the order of $R$ in $A$. The order of $R'$ is $j+1$.
\item Assume that $H(A^{j-1})$ is bounded.
\item Let $\Gamma(R')$ denote the set of descendents of  $R$ in history($A$) that are killed by $R'$. 
The deletion algorithm ensures that $\Gamma(R')$ is available to us prior to rotation. The nodes in 
$\Gamma(R')$ correspond to the vertices of cap($R$) that are adjacent to $R$ and are in conflict 
with $R'$. These vertices lie on the boundary $\partial R$ and they also lie within the component $\bar R'$
\end{enumerate} 
\textbf{Analysis}
History($M$) can be used for locating the optimum of linear function on $H(M)$.
 The cost of query location is $O(\log^{2}m)$ for most ordering of the objects
 in $M$. \\
\textbf{Theorem} The expected cost of a random update on history($M$) and the convex polytope 
$H(M)$ is $O(\log{m})$. The cost of locating the optimum of linear function on $H(M)$ is $O(\log^{2}m)$ for most update sequences.
\subsection{Trapezoidal decompositions}
This is another point locating algorithm for trapezoidal decompositions that 
is based on the technique of deletion via rotations. The query time here is better
by a query factor.
Let $A$ be any ordered set of segments. Let $R$ and $R'$ be any two consecutive segments in the 
ordering on $A$. Assume that they do not commute. Let $\bar A$ be the order obtained from 
$A$ by switching the orders of $R$ and $R'$.\\
\textbf{History update}
\begin{enumerate}
\item Let $j$ be the order of $R$ in $A$. The order of $R'$ is $j+1$. 
\item Let $\Gamma(R')$ denote the set of the descendents of $R$ in history($A$)
that are killed by $R'$.
\item Let $\pi$ denote the nodes corresponding to the trapezoids in $H(A^{j-1})$
in conflict with both $R$ and $R'$. the nodes in $\pi$ can be accessed through
the parent pointers associated with the trapezoids in $\Gamma(R')$.
this takes time proportional to $\sum_{\triangle}$ face-length($\triangle$),
where $\triangle$ ranges over all trapezoids in $\Gamma(R')$.
\end{enumerate}
\textbf{Analysis}
The expected cost of rotation during a random deletion is bounded within a 
logarithmic factor by
\begin{displaymath}
\frac{1}{m}\sum_{i}1+\frac{i}{m^2}I(m)\leq{1}+\frac{I(M)}{m}.
\end{displaymath}
The expected cost of random addition to $M$ is bounded. It is $O(\log{m}+I(M')/m)$,
where $M'$ is the resulting set of segments after addition, and $I(M')$ denotes 
the number of intersection among the segments in $M'$. The logarithmic term reflects
the cost of locating an endpoint of the added segment. \\
\textbf{Theorem} The expected cost of random deletion from history($M$) is 
$O([1+I(M)/m]\log{m})$. The expected cost of random addition to history($M$) 
is $O(\log{m}+I(M')/{m})$, where $M'$ is the resulting set of segments after 
addition. It follows that the expected cost of executing a random sequence is
$O(n\log{n}+I\log{n})$, where $I$ is the number of intersections among the 
segments in $N$. The cost of point location using history($M$) is $O(\log{m})$
for most update sequences.
\section{Dynamic shuffling}
All the previous techniques for point location queries provide no guarantee on
the query time for all update sequences. For example, consider point location in
trapezoidal decompositions. Let $M$ denote the set of undeleted segments existing
at any time. The cost of point location using history($M$) is $O(\log{m})$ on 
most update sequences. That is if the order of addition of segments in $M$ were
random, then the cost of point location would be $O(\log{m})$ with very high
probability. The order of additions is governed by the actual update sequences. 
This would be the same as saying that the cost of point location is $O(\log{m})$
for all update sequences but a $a(1/g(m))th$ fraction of the update sequences,
where $g(m)$ is a large degree polynomial. 

This section introduces a technique
called dynamic shuffling, which generalizes the dynamization technique underlying 
randomized binary trees. It will ensure good query cost with high probability for
ever update sequence.

Let $M$ denote the set of undeleted objects existing at any time. We recall how 
history($M$) was defined. We imagined adding the objects in $M$ in the same 
order as the actual update sequence. History($M$) recorded the history of this 
sequence of addition. We choose a random ordering of objects in $M$. This order 
is completely independent of the actual order in which the objects in $M$ were 
added. We now record the history of this imaginary sequence of additions.

Deletion of object $S$ from shuffle($M$), History($M$) using the shuffle
technique, is just deletion from history($M$). First bring $S$ to the end of the 
order and delete it. 

Addition is different. Consider adding a new segment $S$
to shuffle($M$). Let $M'$=$M\cup${$S$}. We choose a priority for $S$ randomly and
independently from the uniform distribution on the interval[0,1]. After this,
the addition operation is just reversing of the deletion operation. First, 
imagine that $S$ has the highest priority in $M$. Accordingly, we add $S$ 
to the end just like we add $S$ to history($M$). This will yield shuffle($M'$)
where $S$ has the highest priority. After this we use rotation, like the deletion
operation but backward direction until $S$ is in the proper place in the priority
order.\\
\textbf{Analysis}
We want to get the expected cost of maintaining this structure during a random
sequence. Since shuffle($M$) records the history of random sequence we conclude;
\\
\textbf{Theorem} the total expected structural change during the deletion of a
random object from shuffle($M$) is bounded, within a constant factor, by
$(\frac{1}{m})\sum_{i=1}^{m}e(i, M)/i$.
\\
\textbf{Theorem}
The expected total structural change in rotations, as we pass from shuffle($M$) to
shuffle($M'$), is bounded, by a constant factor,\\
$(1/m')\sum_{i=1}^{m'}e(i,M')/i$.
Here, it is assumed that each object in $M'$ is equally likely to occr as an added object.
Combining the the last two theorems;
\\
\textbf{Theorem}
The cost of maintaining shuffle($M$) on a random sequence is
\begin{displaymath}
\sum_{j=1}^{|\bar u|}\frac{1}{r(j)}\sum_{i=1}^{r=j}\frac{e(i)}{i}, \textrm{ where } e(i)=e(i, N).
\end{displaymath}	
\end{document}





