\documentstyle[12pt]{article}
%\textheight=9in
%\textwidth = 7.5in
%\hoffset -.25in
%\voffset -.6in
%\setlength{\parskip}{.15in}
%\setlength{\parindent}{0.5in}
%\renewcommand{\baselinestretch}{1.3}

\begin{document}
{\huge \title{\bf COMPUTATIONAL GEOMETRY}}
\author{95.508 Fall 1997\\  Instructor: Anil Maheshwari\\
School of Computer Science\\ Carleton University\\
 E-mail: maheshwa@scs.carleton.ca}
\maketitle

\section{Purpose}

The purpose of this course is to become familiar with the
field of Computational Geometry. During this course we
will cover fundamental geometric algorithms, which include
convex hulls, Voronoi Diagrams, Trapezoidation, Delaunay triangulation,
line segment intersection, range searching, point location, arrangements.
Also, we will learn about important techniques such as Plane Sweep,
Randomized Incremental Construction, Randomized Divide and Conquer and
Linear Programming.

\section{References}

\begin{enumerate}
\item Preparata and Shamos, {\it An introduction to Computational Geometry},
Springer-Verlag, 1985.

\item Ketan Mulmuley, {\it Computational Geometry: An introduction using 
randomization}, Prentice Hall, 1994.

\item M. de Berg et al., {\it Computational Geometry: Algorithms and Applications}, 

\item Mount, {\it Class notes}, $<$http://www.cs.umd.edu$>$, Spring 1994.

\item Several Research Articles, mainly appearing in following Journals and
Conferences:\\
Discrete and Computational Geometry\\
Computational Geometry: Theory and Applications\\
Algorithmica\\
SIAM Jl. Computing\\
ACM CG\\
CCCG\\
SODA\\
ESA\\
FOCS\\
STOC.

\item Feller, {\it An Introduction to probability theory and its applications},
Vols 1 \& 2,   New York, Wiley. 
\end{enumerate}


\section{Evaluation}

There will be four components, with the following weights.

\begin{enumerate}
\item Seminar 20\%.
\item Report  20\%.
\item Assignments 20\%.
\item Final   40\%.
\end{enumerate}

There will be a Seminar of about 1 hour or more (depends upon the
number of students) and I will give out the topic/and references.
You need to write a detailed report on your seminar in LaTeX.
I will let you know more on this, i.e. its format, depth, etc.


\section{Contact Hours}

Wednesdays: 2:30 to 5:30pm. I won't keep a fixed office hour. Its best
to send me an e-mail and we can fix-up a meeting 
(please avoid Tuesdays for office hours).

\section{Tentative Time Table}

\begin{enumerate}

\item Introduction, What is CG, Examples of CG Problems,
      Model of Computation,  Convex Hulls.

\item Arrangement of Lines.  Plane Sweep - Trapezoidation and Closest Pair. 

\item Skip Lists and Randomized Incremental Construction.  Trapezoidation 
      Revisted.

\item Voronoi Diagrams and Delaunay Triangulation. 

\item Planar Point Location. 

\item Visibility Problems.

\item Motion Planning Problems/Spanners.

\item Range Searching.

\item Linear Programming.

\item Random Sampling.

\item Parallel Algorithms in Computational Geometry.

\item External Memory Algorithms in Computational Geometry.

\end{enumerate}

\end{document}

