From 40d284db59ce2171436f5f04e188e174dfaa8a4e Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bj=C3=B8rn=20Rustad?= Date: Mon, 17 Nov 2014 20:32:32 +0100 Subject: [PATCH] LAME --- fig/area_proof.tex | 4 +-- fig/curve_edge.tex | 44 ++++++++++++--------------------- theory.tex | 61 ++++++++++++++++++++++++++++++++++------------ 3 files changed, 63 insertions(+), 46 deletions(-) diff --git a/fig/area_proof.tex b/fig/area_proof.tex index ed74ea2..a819764 100644 --- a/fig/area_proof.tex +++ b/fig/area_proof.tex @@ -62,8 +62,6 @@ \caption{ A visual argument that $\delta^2 = \Delta \rho \norm{e}$. If extended to the whole plane, there will be the same amount of blue squares as - red squares, so their area must be equal. We have assumed a - reasonable discretization of the set of lines, such that $\Delta - \rho$ is equal and minimal for each family of lines. + red squares, so their area must be equal. } \label{fig:area_proof} diff --git a/fig/curve_edge.tex b/fig/curve_edge.tex index 0ee8711..5446e8e 100644 --- a/fig/curve_edge.tex +++ b/fig/curve_edge.tex @@ -1,33 +1,22 @@ \centering -\begin{tikzpicture}[scale=1.2] - \foreach \x in {0,...,5} { - \foreach \y in {0,...,5} { +\begin{tikzpicture}[scale=2.0] + \foreach \x in {0,...,2} { + \foreach \y in {0,...,2} { \node[tiny vertex] (\x\y) at (\x, \y) {}; } } - \clip (0, 0) rectangle (5, 5); + \clip (0, 0) rectangle (2, 2); - \path[nedge=4cm] (0,5) -- (2,4); - \path[nedge=4cm] (0,4) -- (2,3); - \path[nedge=4cm] (0,3) -- (2,2); - \path[nedge=4cm] (0,2) -- (2,1); - \path[nedge=4cm] (0,1) -- (2,0); + \path[nedge=4cm] (0,0) -- (2,2); + \path[nedge=4cm] (0,1) -- (2,3); + \path[nedge=4cm] (1,0) -- (3,2); - \path[nedge=4cm] (-1,1) -- (1,0); + \path (1,1) -- node[anchor=north west] {$b$} (2,2); + \path (0,0) -- node[anchor=south east] {$a$} (1,1); - \path[nedge=4cm] (1,5) -- (3,4); - \path[nedge=4cm] (1,4) -- (3,3); - \path[nedge=4cm] (1,3) -- (3,2); - \path[nedge=4cm] (1,2) -- (3,1); - \path[nedge=4cm] (1,1) -- (3,0); - - \path[nedge=4cm] (2,5) -- (4,4); - \path[nedge=4cm] (3,5) -- (5,4); - \path[nedge=4cm] (4,5) -- (6,4); - - \draw [cyan, xshift=4cm] plot [smooth, tension=2] coordinates { - (1,1) (2,1) (5,5) (3,3)}; + \draw[cyan, very thick] plot [smooth, tension=1] coordinates { + (-1,1.0) (0.5,0.2) (0.8,1.4) (2,1.5)}; %\path[dash] (2, 2) -- (5,2); %\path[dash] (2, 2) -- (5,5); @@ -58,11 +47,10 @@ %\path[edge] (a) -- (h); %\path[edge] (a) -- (i); - \path (4,1) [edge, <->, anchor=center] -- node[anchor=south - east,yshift=-3.5pt] - {$\Delta \rho$} - ($(5,0)!(4,1)!(3,1)$) ; - \end{tikzpicture} -\caption{One family of lines having the same $\phi$ parameter.} +\caption{ + Here our intersection approximation would not be correct, as only + the intersection with edge $b$ is counted in \fixme{ref}, even + though the curve intersects edge $a$ twice. +} \label{fig:curve_edge} diff --git a/theory.tex b/theory.tex index 58bcf39..fa99250 100644 --- a/theory.tex +++ b/theory.tex @@ -1120,15 +1120,13 @@ later, and thus for an edge $e$ we will consider only the question of ``did $e$ cross $C$ or not?'' This amounts to checking whether the terminals of $e$ lie on each side of the perimeter $C$, and the approximation is exact for zero or one intersection points, but will, as -we see in Figure \fixme{ref}, not be entirely correct when we have more. +we see in Figure \ref{fig:curve_edge}, not be entirely correct when we +have more. \begin{figure} \input{fig/curve_edge} \end{figure} -\fixme{curve or perimeter here, maybe perimeter because then we know it -follows the boundaries of the pixels.} - The second difficulty is that in the discrete setting, we will only have an approximation of the metric tensor $M(x)$ for each point $x \in \mathcal{G}$, and it is thus not available for arbitrary intersection @@ -1141,41 +1139,74 @@ $x$ somewhere on the edge $e_{ab}$, we approximate the metric tensor by \end{equation} the component-wise average of the tensors in the two end points of the edge. \fixme{really? componentwise? will that not mess up the -eigenvalues?} +eigenvalues? sure, a bit, but it won't change consistency..} + +\fixme{ + we must define what we mean by a reasonable line family. meaning + each line goes through more than one grid point. and there are no + grid points withoug a line through it +} \begin{figure} \input{fig/area_proof} \end{figure} + +\begin{lemma} For each family of lines given by an angle parameter $\phi$ we have the relation \begin{equation} - \Delta \rho = \delta^2 / \norm{e}, + \delta^2 = \norm{e} \Delta \rho \end{equation} -which is easy to verify for simple angles $\phi$. For a general argument +\end{lemma} +\begin{proof} + Consider two partitions of the plane $\mathbb{R}^2$ as shown in + Figure \ref{fig:area_proof}. The blue squares area $\delta^2$, + while the red rectangles have length $\norm{e}$ and width $\Delta + rho$. The blue grid repeats with a period of $\delta$ in both + directions. Each grid point is also the terminal of two edges going + each in the directions $\phi$ and $-\phi$. And also from each grid + point we draw a line of length $\Delta \rho$ to the next line. From + this construction, the red partition is also periodic with period + $\delta$ in both directions. + + Consider a \fixme{donut} tile of size $\delta \cdot \delta$ where + the left side is connected to the right, and the top to the bottom. + + We can use a tile of size $\delta \cdot \delta$ of the original red + and blue partition to partition this \fixme{donut} tile as well. +\end{proof} +\begin{proof} + This is easy to verify for simple angles $\phi = \{0, + \sfrac{\pi}{4}, \sfrac{\pi}{2}, \hdots\}$. For a general argument consider the Figure \ref{fig:area_proof}, and call the blue squares $\delta$-squares, and the red rectangles $\rho$-rectangles. The $\delta$-squares have area $\delta^2$, while the $\rho$-rectangles have area $\Delta \rho \cdot \abs{e}$. Our goal is to show that these are equal. First note that we have a periodicity in both directions with period -$\delta$. Thus each $\delta$-square looks exactly the same. Further, -each $\rho$-rectangle is partitioned by blue lines into the similar -parts such that +$\delta$, and each $\delta$-square looks exactly the same. Further, +each $\rho$-rectangle is partitioned by the blue grid into the +subsets $A_i$ such that \begin{equation} - A = \bigcup_{i=1}^{i \leq m} A_i + A = \bigcup_{i=1}^{i \leq m} A_i, \end{equation} -where $A$ is the set of points in a $\rho$-rectangle and $A_i$ is one of -its parts. Since all $\delta$-squares look the same, we can find all +where $A$ is the set of points in a $\rho$-rectangle. All +$\rho$-rectangles start in a grid point, so the will decompose in the +same way. Since all $\delta$-squares look the same, we can find all $A_i$ in a given $\delta$-square such that \begin{equation} \delta^2 \geq \abs{\bigcup_{i=1}^{i \leq m} A_i} = \Delta \rho \abs{e}. \end{equation} -Since the $\rho$-rectangles are a partition of the plane, each point in +Further the $\rho$-rectangles partition the plane and thus each point in a $\delta$-square is also in a $\rho$-rectangle, and each $\rho$-rectangle consists of the same parts $A_i$, and thus \begin{equation} \delta^2 \leq \abs{\bigcup_{i=1}^{i \leq m} A_i} = \Delta \rho \abs{e}. \end{equation} -We can then conclude that $\delta^2 = \Delta \rho \abs{e}$. Inserting +\fixme{we are missing some argument that we don't have more than one +$A_i$ in the square} +We can then conclude that $\delta^2 = \Delta \rho \abs{e}$. +\end{proof} +Inserting this into the curve length approximation we obtain \begin{equation} \abs{C}_M \approx \sum_{e \cap C} \frac{\det M(e) \norm{e}^2 -- 2.47.3