1_Wang.tex

\documentclass{article}
\usepackage{graphicx,amsmath,amsthm,amssymb}
\usepackage{fullpage}
\usepackage{eucal}
\usepackage{graphicx}
\usepackage{color}
\usepackage{tikz}
\usepackage{algorithm,algorithmic}

\newcommand{\question}[1]{\vspace{10pt}\noindent $\mathbf{#1}$}
\newcommand{\R}{\mathbb{R}}
\newcommand{\vect}[2]{\bigl[\begin{smallmatrix}#1\\#2\end{smallmatrix}\bigr]}
\newcommand{\vectt}[3]{\bigl[\begin{smallmatrix}#1\\#2\\#3\end{smallmatrix}\bigr]}
\newcommand{\gap}{{~~~~~~~~~~~~~~~~~~~~~}}

\title{Computational Geometry Homework 1}
\author{hongxuwang}

\begin{document}
  \maketitle

  \section*{Administration}
    Your answers should be typeset in LaTeX or some equivalent and submitted as a \textbf{pdf}.
    The LaTeX sourse of these questions may be found on the course website under ``homework''.
    Name your files as ``3\_\emph{your\_last\_name}.pdf'', all lowercase letters.
    For example, I would call mine \textbf{1\_sheehy.pdf}.

    Submission:  Create a private repository on github.uconn.edu and add me (userid: she13001) as a collaborator.  Name your repository ``your\_last\_name\_compgeom'' (all lowercase).

    \textbf{Checkin by midnight, October 19: Add the pdf to the repository.  I will pull your changes and check in my comments directly on your pdf file.}

  \section{Triangulating Polygons} % (fold)
  \label{sec:triangulating_polygons}

    In class, we showed that every simple polygon can be triangulated.
    The proof was constructive and recursive.
    We showed that as long as the polygon has more than $3$ edges, you can add a ``chord'', an edge through the interior connecting non adjacent vertices that splits the polygon into two smaller simple polygons.
    Suppose we built a binary tree, where the root is the original polygon and the two smaller polygons are the children.  Repeat this recursively.

    \question{1}
    \question{1}
    Prove that every simple polygon with $n$ edges admits such a tree with depth $O(\log n)$.
    Answer:We will prove this using the induction method,for n=3 we would have a tree with depth one.And for n=4 we have a tree with $2=\log 4 $ depth\\
    we assume that for all of the k<n, we have the simple ploygon with $k$ edge have admits a tree with depth $O(\log k)$\\
    so for k=n, we can separate it into two simple polygon, s.t. at least one polygon with a edge $n/2$ \\
    so this this subtree, from our induction, we would have a tree with depth $O(\log n/2)$. \\
    Thus this total tree, we have a  big trees in $O(\log n/2)+1=O(\log n)$ depth.\\
    \question{2}
    Give an example of a simple polygon that only has one triangulation.\\
    \begin{center}
    \includegraphics[width=3.00in,height=2.0in]{Q2G1.jpg}
    \end{center}
    for this question, we can construct a polygon with n edges from a polygon which also have one triangulation in $1n-1$  edges\\
    Answer:firstly, we would see some simple example. From the picture above.\\
    (1)Exactly, every triangle have only one triangulation.\\
    (2)For a quadrilateral, we draw a line BD to make sure that B can not have a inner connection to A.So we got a triangle and a previous triangulation.\\
    (3)For a polygon with five edges, we can delete the edge CD and draw new lines CE and DE which D can not inner connect to A.So for this polygon, we have a triangle CDE and a simple polygon with $n=4$  edges.\\
    (4)For a polygon with six edges, we use the same method (2), we draw a line BF to convince that F can not inner connect to A and E,\\
    for this polygon we can have a triangle BDF and a polygon with $n=5$ edges.\\
    we can use this kind of method to construct $edges==n$ polygon, If n is a odd number,we have a picture as follows.\\
    \begin{center}
    \includegraphics[width=5.00in,height=2.0in]{Q2G2.jpg}
    \end{center}
    In this situation, we can draw a new line AC which that C can not inner connect to P1,P2...Pk-1.For this situation, we can have a triangle and a n-1 edges polygon which have only one triangulation.\\
    \\ If n is a even number,we also have picture as follows.
    \begin{center}
    \includegraphics[width=5.00in,height=2.0in]{Q2G3.jpg}
    \end{center}
    In this situation, we can delete BC and draw two new lines BPk+1 and Pk+1C, furthermore, we can adjust the location of C to C' to make sure that C can not inner connect to P1... Pk.So we should have polygon Pk,Pk+1,C and a polygon with n-1 edges.\\
    Using this method, we can have a polygon which has one triangulation for any random n. \\
    \question{3}
    Suppose you have a simple polygon given as a sequence vertices $(p_1,\ldots,p_n)$ in counter-clockwise order.
    Suppose further that you are given a point $x$ such that $ccw(p_{i-1}, p_i, x) = 1$ for all $i = 1\ldots n$, where $p_0 = p_n$.
    Give an O(n)-time algorithm to find a triangulation of such a polygon.\\
    Firstly, we can calculate the distance from the each edge to x in $O(N)$ times, and we can find the minimum one.Suppose that we have Pi and Pi+1 which is the minimum one. We can draw two lines Pi and Pi+1.So we have a new polygon with $n+1$ edges and a triangle Pi,X,Pi+1.So we should find a triangulation for this polygon.\\
    As the triangulation of this polyhedral, we should use the method as follows\\
    Triangulation(p1,p2,p3...pn)\\
    \{Pn+k=Pk\\
    if n=3$~$ return this triangulation;\\
    for i in range(1,n)\\
    \{\\
    If line P1Pi is inside the polygon\\
    {\\
     draw a line P1PiTriangulation(p2...pi,p1);\\
     triangulation(p2,p3...pi);\\
     triangulation(pi+1,pi+2...pn);\\
    break this circulation;\\
     }\\
    \}\\
    \}\\
  % section triangulating_polygons (end)

  \section{Predicates} % (fold)
  \label{sec:predicates}

  \question{4}
  Use the ccw test to check if two line segments intersect.  Be sure to handle the degenerate cases where some of the points are collinear.\\
 Answer:Suppose we have two segment ab and cd for these two segments, we should firstly test whether 3 points are co-liner.We should test whether CCW(a,b,c) and CCW(a,b,c),CCW(c,d,a) and CCW(c,d,b) is\\
  equal to zero.If there exist a co-liner situation,we assume that abc are co-liner.the picture as follows.We should test whether CCW(A,C,D)==CCW(B,C,D).IF yes, these two segment are not inter sect,If no, they\\
  are truly intersect.And if CCW(A,C,D)=CCW(B,C,D)==0, we should test B or D is inside the  segment AB.
  \begin{center}
  \includegraphics[width=5.00in,height=2.0in]{Q4G1.jpg}
  \end{center}
  And if there is no co-liner between  these two segment.We should test whether CCW(A,B,C)==CCW(A,B,D).If yes, there is no intersect and if no, there is a intersect.\\
  \question{5}
  Write a linear predicate to test if a line segment intersects a triangle in $\R^3$.\\
  Firstly, we assume that we have a triangle xyz and a line segment ab.\\
  We should test CCW(x,y,z,a)==CCW(x,y,z,b) and there are three possibilities.\\
  (1)CCW(x,y,z,a)=CCW(x,y,z,b)$\not=$0, it shows that a and b are in the same side the plane xyz, so there must no intersect.\\
  (2)CCW(x,y,z,a) or CCW(x,y,z,b)=0,we assume that CCW(x,y,z,a)=0,we have a x-y projection for these three points,x',y',z',a'\\
  we should test whether $\frac {CCW(x',y',a')}{CCW(x',y',z')}$==$\frac {CCW(y',z',a')}{CCW(x',y',z')}$==$\frac {CCW(z',x',a')}{CCW(x',y',z')}$==1 or each of them is equal to zero.\\
  If yes, there is a intersect which is a. IF no, there is no intersect between triangle and segment.\\
  (3)if CCW(x,y,z,a)$\not=$CCW(x,y,z,b),it show that a,b are in the different of the plane xyz.\\
  we should test
\[
\left\{
\begin{aligned}
&CCW(a,b,x,z)\not=CCW(a,b,x,y)~ or ~ CCW(a,b,x,z)==0~ or~ CCW(a,b,x,y)==0\\
&CCW(a,b,y,z)\not=CCW(a,b,y,x~ or~ CCW(a,b,y,z)==0 ~or ~ CCW(a,b,y,x==0\\
&CCW(a,b,z,x)\not=CCW(a,b,z,y)~or~ CCW(a,b,z,x)==0 ~or~ CCW(a,b,z,y)==0
\end{aligned}
\right.
\]
if all of the items are true, there exist a intersect.\\
  \question{6}
  Write a function that takes a triangle and line segment as input and returns their intersection point if it exists.  You may assume no $4$ of the points are coplanar.\\
For this question, we can use the method in Q(5) to decide that whether there exist a intersect. If there exist a intersect.We assume that the intersect point is\\
c.We have a q equation that
\[
\left\{
\begin{aligned}
&CCW(a,b,c)=0\\
&CCW(x,y,z,c)=0
\end{aligned}
\right.
\]
we can solve this equation and get c.\\
  % section predicates (end0)

  \section{PSLGs} % (fold)
  \label{sec:pslgs}

    Suppose you are given a PSLG that is guaranteed to have a triangle outer face and every other face is either a triangle or a quadrilateral.
    The vertices are points in the plane with $x$ and $y$ coordinates.
    The half-edges are given, one of which is designated as the \texttt{root} so that you have a handle into the structure.
    The faces are implicit.
    Moreover, the half-edges also store an integer that can be used for traversal.

    \question{7}
    If you know the number of vertices and half-edges, can tell how many of the faces are quadrilaterals?  If so, how many?
    For this question, we have that $\|V\|$=n and $\|hulf-edge\|$=n\\ we have the equation that
    \[
    \left\{
    \begin{aligned}
    &V-E+F=2\\
    &3F_{tri}+4F_{qua}=2*E
    \end{aligned}
    \right.
    \]
    which means that
    \[
    \left\{
    \begin{aligned}
    &m- \frac{n}{2}+F_{tri}+F_{qua}=2\\
    &F_{tri}+F_{qua}=n
    \end{aligned}
    \right.
    \]
    Thus,we have $F_{tri}$=8+n-4m\\
    \question{8}
    Give an algorithm that transforms the PSLG into a polyhedral complex by making the fewest possible changes.\\
    we can travel all of the half-edge structure,it has two possibilities\\
    (1)for a half-edge p1,p2=p1.next,p3=p2.next,p3=p1.it is a triangle.\\
    (2)for a half-edge p1,p2=p1.next,p3=p2.next,p4=p3.next,p4=p1,it is a quadrilateral.\\
    We ignore the triangle,and think about the quadrilateral.there are two possibilities.the pictures shows as follows.\\
   \begin{center}
   \includegraphics[width=5.00in,height=2.0in]{Q8G1.jpg}
   \end{center}
   for situation 1,we do not need to change it.It is a polyhedral complex, for situation2, we need to draw line AC,and make it to become a polyhedral complex.\\
   Thus,we need to test whether $CCW(p1,p2,p3)==CCW(p2,p3,p4)==CCW(p2,p3,p4)==1$.If yes, it is a polyhedral complex,if not, we suppose that CCW(p1,p2,p3)=-1,we draw a line between p2 and p4\\
   Useing this method for all of the  quadrilateral.Finally,we got a polyhedral complex.\\
  % section pslgs (end)


\end{document}