\input tbasic
% this is cs445.tex of January 4, 1982 9:07 AM
% Renamed CS445H0.tex in January 6, 1982 4:24 PM
\font=←timesromanb at 14truebp
\font<←timesromanb at 12truebp
\font b ← timesromani at 12truebp
\font m ← timesroman at 12truebp
\font p ← timesroman at 8truebp
\font o ← timesromani at 8truebp
\font U = fleur at 28truebp

\def\hbf{\:=}
\def\lbf{\:<}
\def\srm{\:p}
\def\sit{\:o}

\gdef\fpage{T}
\output{\baselineskip 0pt \lineskip 0pt
\hbox{\hskip 0.22truein
\vbox to 0pt{\vskip -0.54truein
\if T\fpage {\hbox to size {\rm \hfil}}
\else {\hbox to size {\lbf CS445\hfil Course Topics\hfil\count0}}
\vskip 4 pt
\hrule
\vskip 3 pt
\hrule
\vskip 0.33truein plus 6 in minus 6 in
}
}
\hbox{\hskip 0.22truein\vbox{\page}}
\advcount0
\if T\fpage {\gdef\fpage{F}} \else {}
}

\jpar 1000

\parindent 0pt

\hbox to size {
\hfill
\vbox {
\hbox to 3.5 in {\ctr{\curfont m New Course in Computer Science}}
\vskip .25 in
\hbox to 3.5 in {\ctr{\curfont b CS445 (winter quarter 1981-82)}}
\hbox to 3.5 in {\ctr{\it Tu, Th at 2:45 p.m., in 380U}}
\vskip .25 in
\hbox to 3.5 in {\ctr{\curfont = Computational Geometry}}
\vskip .25 in
\hbox to 3.5 in {\ctr{\curfont m Instructor: Leo Guibas}}
\vskip .1 in
}
}

\vskip .16 in
\hrule height 2 pt
\vskip .16 in

\def\t{\hskip .3 in}
\halign { \lft{#}\cr
<==<small1.press<\cr
{\it Convexity and Star-Shapedness}\cr
\t survey of convex hull algorithms (Graham, Jarvis, Shamos--Hoey and Preparata)\cr
\t on-line hull algorithms (Shamos, Overmars and van Leeuwen)\cr
\t hull of a simple polygon (Graham and F. Yao)\cr
\t average case algorithms (Floyd, Eddy)\cr
\t stochastic properties of convex hulls (Santalo)\cr
\t convex hull in 3 and higher dimensions (Preparata and Hong)\cr
\t lower bounds (A. Yao)\cr
\t hull applications: depth of a set, supporting lines, clustering, numerical analysis, etc.\cr
\t half-plane intersections and kernel computations (Shamos)\cr
\t kernel of a simple polygon (Lee and Preparata)\cr
\cr
{\it Intersection and Inclusion Problems}\cr
\t line segment intersection (Shamos and Hoey, Bentley and Ottman)\cr
\t rectangle intersection (McCreight)\cr
\t range queries (Bentley, Shamos, Fredman)\cr
\t polygon intersection (Shamos, Chazelle and Dobkin)\cr
\t point and polygon inclusion (Shamos)\cr
\t point location in a planar subdivision (Lee and Preparata)\cr
\t separability of point sets, or polygons\cr
\t dynamic and on-line versions of the above\cr
\cr
{\it Union/Decomposition Problems}\cr
\t decomposition of a polygon into triangles, rectangles, trapezoids,\cr
\t \t monotone, and/or convex pieces (Garey, Johnson, Preparata, and Tarjan, Greene)\cr
\t rectagons and rectangle unions (Guibas, Lipton, Karp)\cr
\t decomposition of polyhedra (Weber)\cr
\t point-set triangulation, possibly with weights\cr
\cr
{\it Proximity Problems}\cr
\t $k$-$d$ trees (Bentley)\cr
\t Voronoi diagram for a collection of points (Shamos and Hoey, Kirkpatrick, Drysdale and Lee)\cr
\t furthest point Voronoi, $k$-Voronoi (Lee)\cr
\t applications\cr
\cr
\cr %delete me
{\it Extremal Problems}\cr
\t extremal $k$-gon with vertices among a given collection of points\cr
\t \t (max/min, perimeter/area) (Boyce, Dobkin, Drysdale, and Guibas)\cr
\t minimum spanning and Steiner trees (Shamos)\cr
\t extremal circle problems\cr
\t linear and integer programming\cr
\cr
{\it Geometric Sorting}\cr
\t extrema of a set of points (Kung, Lucchio, and Preparata)\cr
\t rectangle motions, visibility questions, and priority orderings (Guibas and F. Yao)\cr
\t testing partial orders for planarity (F. Yao)\cr
\t history (Munro, Dobkin, and Overmars)\cr
\cr
{\it Placement and Routing}\cr
\t planar separators and embeddings of graphs/trees (Lipton and Tarjan,\cr
\t \t Leiserson, Ruzzo and Snyder)\cr
\t routing around a rectangle (La Paugh)\cr
\t river and channel routing (Rivest, et. al., Siegel and Dolev)\cr
}

\vskip .16 in
\hrule height 2 pt
\vskip .16 in

This is an introductory course at the upper undergraduate level. Its aim will be to develop skills in the design and analysis of geometric algorithms. Don’t let the high course number discourage you! The only prerequisite, aside from that elusive quality called mathematical sophistication, is some familiarity with data structures, at the level of CS144.\par

\vfill\end