notes.tex

\documentclass{article}
\usepackage{algpseudocode} 
\title{Circle Packing Notes}
\author{Kevin Pratt}
\begin{document}
\maketitle

\section{Circle packing quantities}

Quantities: springs, primal radii, dual radii, embeddings, face incircles, face orthocircles.

From the springs an embedding can be found. If this embedding is a circle packing, the primal radii can be found from the dual radii(the incircles of each face).

\paragraph{}
You can probably get the primal radii more directly, by using the fact that $k_{uv} = \frac{r_w+r_z}{r_u+r_v}$, for an edge $(u,v)$ perpendicular to the dual edge $(w,z)$. From this we have a system of $f+v=2+e$ unknowns and $e$ equations (what are the stresses for edges on the outer face?). However since each dual radii can be expressed by the three primal radii defining the face (using heron's formula), it's really a nonlinear system of $v$ unknowns and $e$ equations.

\section{Necessary/sufficient circle packing conditions}

The following are necessary conditions for a circle packing:\\
1). For all edges $(u,v)$ perpendicular to the dual edge $(w,z), k_{uv} = \frac{r_w+r_z}{r_u+r_v}$\\
2). The angle sum at all interior verticies is $2\pi$ \\
3). The incircle of each face of is equal to the orthocircle through the three verticies of that face\\
4). For each edge $e_{uv}$ in the embedding, $||e_{uv}||=r_u+r_v$\\

The following are sufficent conditions for a circle packing:\\
1.) The angle sum at all interior verticies is $2\pi$ \\
2). For each edge $e_{uv}$ in the embedding, $||e_{uv}||=r_u+r_v$, and for all edges 
$(u,v), k_{uv}>0$ (and so $k_{uv} = \frac{r_w+r_z}{r_u+r_v}$).\\

\paragraph{Orick's algiorithm}
:\\
1). Compute embedding\\
2). Calculate dual radii for this embedding\\
3). Update primal radii from the dual radii\\
4). Update springs from the primal radii\\

\section{A different kind of algorithm}
Here's a dynamic programming-ish algorithm that uses the fact that if you have a circle packing and would like to add another vertex to its boundary, you can find a mobius transformation of the initial packing that "`makes room"' where you can place the next circle. How to find this transformation, I don't know.
\paragraph{}

Initialization: Select an arbitrary internal face of the triangulation, and manually give it an embedding $E$.\\
1. Take a vertex $v$ that has not been placed and is adjacent to the outer face of the embedded packing, assign it an arbitrary radius, and place it at the origin.
2. Find a mobius transformation of $E$ that positions the outer verticies so that they would be adjacent to $v$ if it were placed.

Suppose you can find a suitable mobius transformation in $f(n)$ time. Then the complexity of this approach is $O(n^2f(n))$, which is worse than Orick's algorithm. There may also be a problem with numerical precision from having to perform n mobius transformations. Also it could generate packings with some radii much bigger than others if you don't pick "`nice"' mobius transformations. 
\end{document}