\documentclass[11pt]{article}
% this is Latex2e

\usepackage{times,timesmt,epsfig}

\setlength{\textwidth}{6in}
\setlength{\textheight}{8.5in}
\setlength{\topmargin}{-.5in}	% top of page to top of running head minus 1in
% \setlength{\headsep}{.5in}	% bottom of running head to top of text
\setlength{\oddsidemargin}{.5in}	% left margin minus 1in on odd pages
\setlength{\evensidemargin}{0in}	% left margin minus 1in on even pages
\setlength{\parskip}{2ex}		% vertical space between paragraphs

\def\prob #1#2 {\begin{figure}[ht] \noindent {\bf \Large #1} [#2] }
\def\endprob #1 {\vskip #1 \end{figure}}
% \def\prob #1#2 {\noindent {\bf \Large #1}[#2]\hskip .7em}
% \def\endprob {\vskip .5in}

\def\gap{\vskip 1ex}
\def\ba{\gap {\bf a)\ \ }}
\def\bb{\gap {\bf b)\ \ }}
\def\bc{\gap {\bf c)\ \ }}
\def\bd{\gap {\bf d)\ \ }}

\begin{document}

\begin{center}
{\LARGE Written Assignment W2}\\
Computer Graphics 2 (15-463)\\
8 Apr. 1999\\
\vskip 2ex
Due 4pm Thursday, {\bf 15 Apr.} at my office (DH 4301A)
or in class that day.
\end{center}

\noindent
Explain your work.
You may use Maple, Mathematica, or other symbolic algebra systems for
this homework, but if you do, turn in a transcript of your session.
\vskip .5in

\prob{1.}{6 pts.}
Let's define a {\it line segment split (LSS) BSP tree}
to be the type of 2-D BSP tree
described in lecture:
it is used to store a set of line segments, and its
splitting lines are the lines through line segments
(similar to the BSP tree figure in Foley, except his set of line segments
always forms a closed polygon).
\ba
What are the shallowest and deepest LSS BSP trees possible with
7 disjoint (not intersecting, not touching), noncolinear line segments?
Draw two views for each case:
give both
a geometric view of the line segments with the split lines passing through
them, dividing the plane into regions (might be useful to use black \& red
here to distinguish line segments from split lines)
and also a view of the BSP tree drawn as a tree with nodes and links.
Label each line segment or node with a number or letter.
See Foley's figure for an example of two such views.
\bb
What are the shallowest and deepest LSS trees possible with
$n$ disjoint, noncolinear line segments?
Give formulas.
\bc
What is the deepest LSS BSP tree possible with $n$ possibly intersecting
line segments?
Give answer in $O()$ notation.
\bd
If we don't restrict ourself to LSS BSP trees, but allow arbitrary splitting
lines, not just lines through a line segment in the set,
how much can this improve the deepest tree you drew in part {\bf a} above?
i.e. draw both views of
the shallowest general BSP tree for this line segment geometry.
\endprob{.5in}

\prob{2.}{12 pts.}
This is the problem from the midterm.
B\'eziers and other polynomials can only approximate a circle,
but {\it rational} polynomials can represent them exactly.
Find a rational polynomial formula for a unit-radius circle.
That is,
let $x(t)=p(t)/r(t)$ and $y(t)=q(t)/r(t)$,
where $p$, $q$, and $r$ are polynomials.
The simplest answer uses quadratic $p$ and linear $q$, so
you can assume the forms $p(t)=t^2+at+b$ and $q(t)=ct+d$ without
much loss of generality.
Note that the parameter $t$ is not proportional to angle.
\ba
What are the conditions on
coefficients $a$, $b$, $c$, and $d$ so that $r$ is a polynomial
and all points on this curve lie on the circle?
\bb
Find constants $a$, $b$, $c$, and $d$ that work (answer is not unique),
and give rational polynomial formulas for $x(t)$ and $y(t)$.
Show your work. (This part of the problem takes a while.)
\bc
What $t$ interval traces out a semicircle?  A full circle?
\endprob{.5in}

\prob{3.}{12 pts}
This problem analyzes uniform grid subdivisions for ray casting.
Assume that there are $s$ surfaces uniformly distributed in a box
which is divided into
an $n \times n \times n$ grid of rectangular voxels,
and the voxels are bigger than the surfaces for the values
of $n$ of interest, so that each surface is listed in no more than 8
voxels' lists.
Let the time to step from one voxel to its neighbor be $t_s$,
and the time to intersect a ray with a surface be $t_i$.
\ba
What is the worst case time cost of intersecting
a ray with the surfaces to find the first intersection point, as a function
of $n$, $s$, $t_s$, and $t_i$.
Your answer should have the units of time, and should not employ $O()$.
For the worst case, keep the assumption that surfaces are uniformly
distributed, (so they wouldn't all lie in one voxel), but find the ray path
that will take the longest to trace.
State your assumptions clearly.
\bb
Graph cost as a function of $n$, qualitatively
(don't worry about constants for the graph, but show its character.
Hint: the curve should be concave upwards and have a minimum, since
intersection testing gets very expensive for $n$ small, and stepping
gets very expensive for $n$ large.
\bc
Where is the minimum, and what is the time cost there?
\endprob{.5in}

\end{document}
