\input PapHdr.tex
\begfile{SubdDY.tex of March 4, 1983 4:27 AM - Stolfi}
\paper{Primitives for the Manipulation of General Subdivisions\ctrpar and the Computation of Voronoi Diagrams\ctrpar\ctrpar FIGURE CAPTIONS}
\def\paptitle{Primitives for Voronoi diagrams}
\def\InCircle{\hbox{\it InCircle}}
\def\lcand{\hbox{\it lcand}}
\def\rcand{\hbox{\it rcand}}
\def\basel{\hbox{\it basel}}
\def\CCW{\hbox{\it CCW}}
\def\cross{\hbox{\it cross}}
\def\ldi{\hbox{\it ldi}}
\def\rdi{\hbox{\it rdi}}
\def\quadedge{quad edge}
\def\B{\hbox{\curfont W B\/}} % for B↑2
\def\S{\hbox{\curfont W S\/}} % for S↑1
\def\thin{\hskip0.7pt}
\def\sym{\thin\hbox{\it Sym\/}}
\def\flip{\thin\hbox{\it Flip\/}}
\def\rot{\thin\hbox{\it Rot\/}}
\def\onext{\thin\hbox{\it Onext\/}}
\def\oprev{\thin\hbox{\it Oprev\/}}
\def\dnext{\thin\hbox{\it Dnext\/}}
\def\dprev{\thin\hbox{\it Dprev\/}}
\def\lnext{\thin\hbox{\it Lnext\/}}
\def\lprev{\thin\hbox{\it Lprev\/}}
\def\rnext{\thin\hbox{\it Rnext\/}}
\def\rprev{\thin\hbox{\it Rprev\/}}
\def\lef{\thin\hbox{\it Left\/}}
\def\rif{\thin\hbox{\it Right\/}}
\def\org{\thin\hbox{\it Org\/}}
\def\dest{\thin\hbox{\it Dest\/}}
\def\dual{\thin\hbox{\it Dual\/}}
\def\psym{\hbox{\fx .Sym}}
\def\pflip{\hbox{\fx .Flip}}
\def\prot{\hbox{\fx .Rot}}
\def\ponext{\hbox{\fx .Onext}}
\def\poprev{\hbox{\fx .Oprev}}
\def\pdnext{\hbox{\fx .Dnext}}
\def\pdprev{\hbox{\fx .Dprev}}
\def\plnext{\hbox{\fx .Lnext}}
\def\plprev{\hbox{\fx .Lprev}}
\def\prnext{\hbox{\fx .Rnext}}
\def\prprev{\hbox{\fx .Rprev}}
\def\plef{\hbox{\fx .Left}}
\def\prif{\hbox{\fx .Right}}
\def\pnext{\hbox{\fx .Next}}
\def\pdata{\hbox{\fx .Data}}
\def\porg{\hbox{\fx .Org}}
\def\pdest{\hbox{\fx .Dest}}
\def\Si{\Sigma}
\def\Vs{\Vscr}
\def\as{↑\ast}
\def\Es{\Escr}
\def\Ls{\Lscr}
\def\Cs{\Cscr}
\def\Ks{\Kscr}
\def\Ts{\Tscr}
\def\ls{\lscr}
\def\Fs{\Fscr}
%reference macros
\def\Sham{Sh}
\def\Kirki{Ki1}
\def\Kirkii{Ki2}
\def\ShamHo{SH}
\def
\GrSi{GS}
\def\Baum{Ba}
\def\Braid{Br}
\def\IyKa{IK}
\def\MuPr{MP}
\def\MaSu{MS}
\def\Knuth{Kn}
\def\Even{Ev}
\def\Lee{Le}
\def\Har{Har}
\def\PH{PH}
\def\boo#1{
\penalty500
\vskip30pt
\figcap{#1}
\vskip20pt
\hrule
\vskip10pt}
\boo{Figure 1.1. Examples of subdivisions.}
\boo{Figure 1.2. Two subdivisions with isomorphic graphs that are not equivalent.}
\boo{Figure 2.1. The ring of edges out of a vertex.}
\boo{Figure 2.2. A subdivision of the extended plane (solid lines) and a strict dual (dashed lines).}
\boo{Figure 2.3. The edge functions.}
\boo{Figure 3.1. A completion on the extended plane, showing primal links (solid), dual links (dashed) and skew links (dotted).}
\boo{(a) Edge record showing \prg{Next} links.}
\boo{(b) A subdivision of the sphere.}
\boo{(c) The data structure for the subdivision (b).}
\boo{Figure 4.1. The quad-edge data structure.}
\boo{Figure 4.2. An $\onext$ ring with canonical representatives on both sides of the manifold.}
\boo{Figure 5.1. The result of \prg{MakeEdge}.}
\figcap{\hfil$a\org=b\org$, $a\lef\neq b\lef$}
\boo{\hfil\prg{Splice[$a$, $b$]}\hbox to 3cm{\null}}
\boo{\hfil$a\org\neq b\org$, $a\lef=b\lef$}
\boo{Figure 5.2a. The effect of \prg{Splice}: trading a vertex for a face.}
\figcap{\hfil$a\org\neq b\org$, $a\lef\neq b\lef$}
\boo{\hfil\prg{Splice[$a$, $b$]}\hbox to 3cm{\null}}
\figcap{\hfil$a\org=b\org$, $a\lef=b\lef$}
\boo{Figure 5.2b. The effect of \prg{Splice}: Changing the connectivity of the manifold.}
\figcap{\hfil$a\org=b\org\flip$, $a\lef\neq b\lef$}
\boo{\hfil\prg{Splice[$a$, $b$]}\hbox to 3cm{\null}}
\figcap{\hfil$a\org=b\org\flip$, $a\lef=b\lef$}
\figcap{\hfil$c\lef=b\lef\flip$, $c\org=b\org$}
\boo{\hfil\prg{Splice[$c$, $b$]}\hbox to 3cm{\null}}
\figcap{\hfil$c\lef=b\lef\flip$, $c\org\neq b\org$}
\boo{Figure 5.2c. The effect of \prg{Splice}: Adding or removing a cross-cap.}
\boo{\hbox to 2cm{}Case 1.\hfil Case 2.\hbox to 2cm{}\hfilneg}
\figcap{\hfil Case 3.}
\boo{Figure 5.3. The effect of \prg{Splice} on the $\onext$ orbits.}
\boo{Figure 5.4. The effect of \prg{SwapEdge[$e$]}.}
\boo{Figure 7.1. The Voronoi diagram (solid) and the Delaunay diagram (dashed).}
\boo{Figure 8.1. The $\InCircle$ test.}
\boo{Figure 8.4. A property of the neighbors of $A$.}
\boo{Figure 8.2. The quadratic map for computing $\InCircle$.}
\boo{Figure 8.3. The set of circles passing through two given points.}
\boo{Figure 8.5. A property of the Delaunay diagram.}
\boo{Figure 9.1. The structure of the $L$--$R$ edges.}
\boo{Figure 9.2. The variables \prg{lcand}, \prg{rcand}, and \prg{basel}.}
\boo{Figure 9.3. The rising bubble.}
\boo{Figure 9.4. End of \prg{lcand} loop.}
\boo{Figure 10.1. A circle proving the ``Delaunayhood’’ of $XC$.}
\boo{Figure 10.2. Proving correctness of the incremental method.}
\par\vfill\eject\end