3_tan.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}{{~~~~~~~~~~~~~~~~~~~~~}}
\newcommand{\vor}{\mathrm{Vor}}
\newcommand{\CC}{\mathrm{conv}}

\title{Computational Geometry Homework 3}
\author{Yiyun Tan}

\begin{document}
  \maketitle
      
  \section*{Projective Duality} 
  
  \question{1}
  Let $a,b\in\R^2$.
  Consider the lifted points $\bar a = \vect{a}{\|a\|^2}$ and $\bar b = \vect{b}{\|b\|^2}$ in $\R^3$.
  Prove that the projection of $\bar{a}^*\cap \bar{b}^*$ is the perpendicular bisector between $a$ and $b$.

  \vspace{1em}  
  If you are feeling ambitious, prove that for $a,b\in\R^d$, the same holds, where the perpendicular bisector of $2$ points in $\R^d$ is a hyperplane.
 
  \vspace{1em}  
 Proof: Firstly we think $a,b\in\R^2$.
 
 Suppose $a$=($x_{1}$,$y_{1}$), $b$=($x_{2}$,$y_{2}$)
 
 And $\bar a = \vect{a}{\|a\|^2}$ and $\bar b = \vect{b}{\|b\|^2}$ in $\R^3$
 
 So $\bar a$=($x_{1}$,$y_{1}$,$x^{2}_{1}+y^{2}_{1}$), $\bar b$=($x_{2}$,$y_{2}$,$x^{2}_{2}+y^{2}_{2}$)
 
 Then $\bar{a}^*$ is $z$=2$x_{1}$x+2$y_{1}$y-($x^{2}_{1}+y^{2}_{1}$), $\bar{b}^*$ is $z$=2$x_{2}$x+2$y_{2}$y-($x^{2}_{2}+y^{2}_{2}$)
 
 So $\bar{a}^*\cap \bar{b}^*$ is 2$x_{1}$x+2$y_{1}$y-($x^{2}_{1}+y^{2}_{1}$) = 2$x_{2}$x+2$y_{2}$y-($x^{2}_{2}+y^{2}_{2}$)
 
 Solve it we can get x=($x_{1}$+$y_{1}$)/2, y=($x_{2}$+$y_{2}$)/2
 
 It is the perpendicular bisector between $a$ and $b$
 
 
 
  \question{2}
  Let $a,b,c\in \R^2$, not all collinear.
  As in the previous question, we lift these points to $\bar a = \vect{a}{\|a\|^2}$, $\bar b = \vect{b}{\|b\|^2}$, and $\bar c = \vect{c}{\|c\|^2}$ in $\R^3$.
  Let $h = \{\bar{x} = \vect{x}{x_z} \mid x_z = 2n^{\top}x - n_z\}$ for $n\in \R^2$ and $n_z\in \R$ be the plane passing thru $\bar{a}$, $\bar{b}$, and $\bar{c}$.
  Prove that $n$ is the circumcenter of $a$, $b$, and $c$.
  
  \vspace{1em}
  \emph{Hint: dualize h, use incidence preservation, and recall that $2n^{\top} a - \|a\|^2 = \|n\|^2 - \|n-a\|^2$.}
  \vspace{1em}
  
  If you are feeling ambitious, consider the following high-dimensional version.
  Let $a_0,\ldots a_d \in \R^d$ and the corresponding lifted points $a_i = \vect{a}{\|a\|^2}$ for $i=0\ldots d$.
  Let $h = \{\bar{x} = \vect{x}{x_z} \mid x_z = 2n^{\top}x - n_z\}$ for $n\in \R^d$ and $n_z\in \R$ be the plane passing thru $\bar{a}$, $\bar{b}$, and $\bar{c}$.
  Prove that $n$ is the circumcenter of $a_0,\ldots, a_d$.
  
  \vspace{1em}  
 Proof: Firstly we think $a,b,c\in\R^2$.
 
 Suppose $a$=($x_{1}$,$y_{1}$), $b$=($x_{2}$,$y_{2}$), $c$=($x_{3}$,$y_{3}$)
 
 So $\bar a$=($x_{1}$,$y_{1}$,$x^{2}_{1}+y^{2}_{1}$), $\bar b$=($x_{2}$,$y_{2}$,$x^{2}_{2}+y^{2}_{2}$), $\bar c$=($x_{3}$,$y_{3}$,$x^{2}_{3}+y^{2}_{3}$)

And $h = \{\bar{x} = \vect{x}{x_z} \mid x_z = 2n^{\top}x - n_z\}$ is the plane passing thru $\bar{a}$, $\bar{b}$, and $\bar{c}$

Also we know $2n^{\top} a - \|a\|^2 = \|n\|^2 - \|n-a\|^2$

Let $a=x$ we have $2n^{\top} x = \|x\|^2 + \|n\|^2 - \|n-x\|^2$

And by dualizing $h$, we have the point ${h}^*= \vect{n^{\top}}{n_{z}}$

Use the conclusion in the previous question, we have the projection of $\bar{a}^*\cap \bar{b}^*$ is the perpendicular bisector between $a$ and $b$, the projection of $\bar{a}^*\cap \bar{c}^*$ is the perpendicular bisector between $a$ and $c$, and projection of $\bar{b}^*\cap \bar{c}^*$ is the perpendicular bisector between $b$ and $c$.

And $n$ also satisfies the above equations

So $n$ is  the projection of $\bar{a}^*\cap \bar{b}^*\cap \bar{c}^*$ 

Q.E.D. $n$ is the circumcenter of $a$, $b$, and $c$.


  
\end{document}