forked from joehuchette/ClutteredEnvPathOpt.jl
/
writeup.tex
60 lines (48 loc) · 1.82 KB
/
writeup.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{algpseudocode}
\title{Writeup}
\author{Miles Olson}
\date{Spring 2020}
\begin{document}
\maketitle
\begin{algorithmic}[1]
\Procedure{Separate}{$G^*, F$}
\State $G \gets copy(G^*)$ \Comment{Construct the finite element graph $G$}
\ForAll{$f \in F$}
\State $V \gets \text{vertices}(f)$
\ForAll{$(i, j) \in V \times V$}
\State $\text{add\_edge}(G, i, j)$
\EndFor
\EndFor
\State $G^{**} \gets copy(G^*)$ \Comment{Construct the planar reduction $G^{**}$}
\State $M \gets \varnothing$
\ForAll{$f \in F$}
\State $\mu \gets \text{some new vertex}$
\State $M[\mu] \gets f$
\State $V \gets \text{vertices}(f)$
\ForAll{$v \in V$}
$\text{add\_edge}(G, v, \mu)$
\EndFor
\EndFor
\State $(A^{**}, B^{**}, C^{**}) \gets \text{planar\_separator}(G^{**})$
\State $A \gets v$ for $v \in A^{**}$ if $v \notin NV$ \Comment{Remove ``bad face'' vertices}
\State $B \gets v$ for $v \in B^{**}$ if $v \notin NV$
\ForAll{$(\mu, f) \in M$}
\If{$\mu \in C^{**}$}
\State $X \gets \text{vertices}(f)$
\State $\chi_a \gets v$ for $v \in X$ if $v \in A^{**}$
\State $\chi_b \gets v$ for $v \in X$ if $v \in B^{**}$
\If{$|\chi_a| < |\chi_b|$}
\State $A \gets A \setminus \chi_a$
\Else
\State $B \gets B \setminus \chi_b$
\EndIf
\EndIf
\EndFor
\State \textbf{return} $(A, B, \text{vertices}(G) \setminus (A \cup B))$
\EndProcedure
\end{algorithmic}
\end{document}