<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{hyperref}
 \usepackage{amsmath,amssymb,color,amsthm,graphicx}

\usepackage[]{algorithm2e}

\usepackage{xcolor}
\pagestyle{empty}

\begin{document}
\begin{center}
CS 763 Fall 2022 \hfill due Wednesday October 5\\
{A.~Lubiw \hfill \quad}
\end{center}

\begin{center}
\large\bf ASSIGNMENT 2
\end{center}

\noindent
ACKNOWLEDGE YOUR SOURCES.

\bigskip
\noindent
\begin{enumerate}

\item{[10 marks]} Convex Hull in 2D.

\begin{enumerate}
\item{[5 marks]}
Give a linear-time algorithm to find the convex hull of the union of
two convex polygons in the plane. 
Your algorithm should handle any pair of convex polygons, disjoint, nested, etc.

{\bf Hint.}  Think about which of the convex hull algorithms we covered in class can be used for this purpose.  Your algorithm should be high-level and brief, but be sure you address correctness and runtime.

\item{[5 marks]}
Given a set $S$ of points in the plane, its ``onion peeling''
consists
of a sequence $H_1, \ldots, H_k$ of convex polygons, where $H_1$ is
the convex hull of $S$, $H_2$ is the convex hull of $S$ with the points
of $H_1$ removed, etc. Draw yourself a picture.  The inner-most points are sometimes used as the ``centers'' of the point set.

Give an $O(n^2)$ time algorithm to find the onion peeling using gift-wrapping (Jarvis's algorithm).  Your algorithm should be high-level and brief, but be sure you address correctness and runtime.


[For your information, but irrelevant for this assignment: There is an $O(n \log n)$ time onion peeling algorithm due to Chazelle.]

\end{enumerate}



\item{[10 marks]}
The \emph{sharpness} of a vertex $v$ of a convex polyhedron in $\mathbb{R}^3$ is $2\pi$ minus the sum of the face angles at  $v$.  For example, a vertex of a cube has 3 face angles each of $\pi /2$, so its sharpness is $2\pi - 3\pi /2  = \pi/2$.
Prove that the sum of the sharpness of all the vertices of a convex polyhedron is $4\pi$.

You will need Euler's formula and one other ingredient.




\end{enumerate}

\end{document}
</pre></body></html>