\documentstyle[11pt]{article}

\newenvironment{mylist}[1]{
\setbox1=\hbox{#1}
\begin{list}{}{
\setlength{\labelwidth}{\wd1}
\setlength{\leftmargin}{\wd1}
  \addtolength{\leftmargin}{1em}
  \addtolength{\leftmargin}{\labelsep}
\setlength{\rightmargin}{1em}}}{\end{list}}

\newcommand{\litem}[1]{\item[#1\hfill]}
\newcommand{\ritem}[1]{\item[#1]}

\newcounter{questnum}
\newcommand{\question}[1]{
\vspace{.1in}
  \refstepcounter{questnum}
{\bf \medskip Problem \thequestnum: }}

\newcommand{\titledquestion}[2]{
 \refstepcounter{questnum}
{\bf \medskip Problem \thequestnum:} #2 {\normalsize (#1 pts) \\}}

\newcommand{\answerspace}{\verb+                                  +
\underline{\makebox[2.0in]{}}}
\newcommand{\smanswerspace}{\underline{\makebox[0.5in]{}}}

\setlength{\topmargin}{-0.5 in}
\setlength{\oddsidemargin}{0 in}
\setlength{\textheight}{8.75 in}
\setlength{\textwidth}{6.5 in}
\setlength{\parindent}{0.0 in}

\begin{document}

{\large 
CS294-3: Algorithms in the real world \hfill Assignment 4 (Triangulation and
N-body)\\[.03in]
Due: Wednesday Nov 5, 1997\\[.1in]
}

Implement one of the algorithms below.  Feel free to work in groups of
two, although I will expect a better job from a group of two.  Also
feel free to come and discuss the algorithms with me.  I've described
each of these algorithms in class and have also made papers available
that describe the algorithms in more detail.  Two of the papers are
available on the web, and the third I will put outside my office to be
copied.

See the web pages for more information on this assignment as it
becomes available (e.g. data sets).

\paragraph{Rupert's Meshing Algorithm:}  You should implement the
algorithm and run it on the test set(s) I will make available and
report back the number of triangles for minimum angles ranging from 15
to 25 degrees in steps of 2 degrees.  Ideally you should generate a
postscript drawing of the final triangulations.  Although the drawings
are not required they will certainly help you debug your program.

\begin{quote}
Jim Rupert.
``A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation.''
Journal of Algorithms, 18(3):548-585, May 1995.
(Available at: {\footnotesize \tt \\
http://science.nas.nasa.gov/Pubs/TechReports/RNRreports/jruppert/RNR-94-002/RNR-94-002.html})
\end{quote}

\paragraph{Garland and Heckbert's Surface Modeling Algorithm:}
You should implement the algorithm and run it on the test set(s)
I will make available and report back the number of triangles
for a range of maximum errors (the range will be data set
dependent).   Again generating a drawing of the triangulation
will be helpful but is not necessary.  The algorithm I want you
to implement is number III in the paper (the version I described in
class).

\begin{quote}
Michael Garland and Paul Heckbert.
``Fast Polygonal Approximation of Terrains and Height Fields.''
CMU-CS-95-181, CS Dept, Carnegie Mellon U., Sept. 1995. \\
(Available at: \verb+http://www.cs.cmu.edu/~garland/scape+)
\end{quote}

\paragraph{Callahan and Kosaraju's Well-Separated Pair Decomposition Algorithm:}
You should implement the algorithm and run it on the Plummer model
(I'll make the equation available) with 10K and 100K points.  For both
sizes you should report the number of interactions as a function of
the separation constant $s$ ranging from 1 to 2 in increments of .2.

\begin{quote}
Paul B. Callahan and S. Rao Kosaraju.  
``A Decomposition of Multi-Dimensional Point-Sets with Applications to k-Nearest-Neighbors and n-Body Potential Fields.''
JACM, 42(1):67-90, January 1995
\end{quote}

\end{document}
