\begin{slide}{violet}
\violet
\begin{center}
simulated annealing
\end{center}
start with minimum spanning tree: 
\begin{tabbing}
xxxxx\=yyyyy\=zzzzz\= \kill
\>easy version: $O(N^2)$ time\\
\>hard version: $O(N log N)$ time
\end{tabbing}

small structure change: add/delete an S-point:\\
add: 
\begin{tabbing}
xxxxx\=yyyyy\=zzzzz\= \kill
\>easy version:\\ 
\>\>consider ${n}\choose{3}$ triples where angles work;\\
\>\>compute S-point for each;\\
\>\>take best;\\
\>\>update MST;\\
\quad\\
\>hard version:\\ 
\>\>oriented Dirichlet cells (Papadimitriou)
\end{tabbing}

delete: regenerate MST
\end{slide}
