text:
# Sufficient Conditions for Tuza's Conjecture on Packing and Covering Triangles

Given a simple graph G=(V,E), a subset of E is called a triangle cover if it intersects each triangle of G. Let ν_t(G) and τ_t(G) denote the maximum number of pairwise edge-disjoint triangles in G and the minimum cardinality of a triangle cover of G, respectively. Tuza conjectured in 1981 that τ_t(G)/ν_t(G)<2 holds for every graph G. In this paper, using a hypergraph approach, we design polynomial-time combinatorial algorithms for finding small triangle covers. These algorithms imply new sufficient conditions for Tuza's conjecture on covering and packing triangles. More precisely, suppose that the set T_G of triangles covers all edges in G. We show that a triangle cover of G with cardinality at most 2ν_t(G) can be found in polynomial time if one of the following conditions is satisfied: (i) ν_t(G)/| T_G|>1/3, (ii) ν_t(G)/|E|>1/4, (iii) |E|/| T_G|>2. Keywords: Triangle cover, Triangle packing, Linear 3-uniform hypergraphs, Combinatorial algorithms

## Authors

• 3 publications
• 2 publications
• 2 publications
• 6 publications
• ### Min-Max Theorems for Packing and Covering Odd (u,v)-trails

We investigate the problem of packing and covering odd (u,v)-trails in a...
08/23/2017 ∙ by Sharat Ibrahimpur, et al. ∙ 0

• ### Ear-Slicing for Matchings in Hypergraphs

We study when a given edge of a factor-critical graph is contained in a ...
12/11/2019 ∙ by András Sebő, et al. ∙ 0

• ### Packing nearly optimal Ramsey R(3,t) graphs

In 1995 Kim famously proved the Ramsey bound R(3,t) > c t^2/ t by constr...
11/16/2017 ∙ by He Guo, et al. ∙ 0

• ### Moving intervals for packing and covering

We study several problems on geometric packing and covering with movemen...
09/01/2021 ∙ by Rain Jiang, et al. ∙ 0

• ### Multi-transversals for Triangles and the Tuza's Conjecture

In this paper, we study a primal and dual relationship about triangles: ...
01/01/2020 ∙ by Parinya Chalermsook, et al. ∙ 0

• ### Minimum T-Joins and Signed-Circuit Covering

Let G be a graph and T be a vertex subset of G with even cardinality. A ...
03/09/2018 ∙ by Yezhou Wu, et al. ∙ 0

• ### Iterated Medial Triangle Subdivision in Surfaces of Constant Curvature

Consider a geodesic triangle on a surface of constant curvature and subd...
07/08/2021 ∙ by Florestan Brunck, et al. ∙ 0

##### This week in AI

Get the week's most popular data science and artificial intelligence research sent straight to your inbox every Saturday.

## 1 Introduction

Graphs considered in this paper are undirected, simple and finite (unless otherwise noted). Given a graph with vertex set and edge set , for convenience, we often identify a triangle in with its edge set. A subset of is called a triangle cover if it intersects each triangle of . Let denote the minimum cardinality of a triangle cover of , referred to as the triangle covering number of . A set of pairwise edge-disjoint triangles in is called a triangle packing of . Let denote the maximum cardinality of a triangle packing of , referred to as the triangle packing number of . It is clear that holds for every graph . Our research is motivated by the following conjecture raised by Tuza [1] in 1981.

###### Conjecture 1.1 (Tuza’s Conjecture [1]).

holds for every graph .

To the best of our knowledge, the conjecture is still unsolved in general. If it is true, then the upper bound 2 is sharp as shown by and – the complete graphs of orders and .

#### Related work.

The only known universal upper bound smaller than 3 was given by Haxell [2], who shown that holds for all graphs . Haxell’s proof [2] implies a polynomial-time algorithm for finding a triangle cover of cardinality at most 66/23 times that of a maximal triangle packing. Other partial results on Tuza’s conjecture concern with special classes of graphs.

Tuza [3] proved his conjecture holds for planar graphs, -free chordal graphs and graphs with vertices and at least edges. The proof for planar graphs [3] gives an elegant polynomial-time algorithm for finding a triangle cover in planar graphs with cardinality at most twice that of a maximal triangle packing. The validity of Tuza’s conjecture on the class of planar graphs was later generalized by Krivelevich [4] to the class of graphs without -subdivision. Haxell and Kohayakawa [5] showed that for tripartite graphs , where . Haxell, Kostochka and Thomasse [6] proved that every -free planar graph satisfies .

Regarding the tightness of the conjectured upper bound 2, Tuza [3] noticed that infinitely many graphs attain the conjectured upper bound . Cui, Haxell and Ma [7] characterized planar graphs satisfying ; these graphs are edge-disjoint unions of ’s plus possibly some vertices and edges that are not in triangles. Baron and Kahn [8] proved that Tuza’s conjecture is asymptotically tight for dense graphs.

Fractional and weighted variants of Conjecture 1.1 were studied in literature. Krivelevich [4] proved two fractional versions of the conjecture: and , where and are the values of an optimal fractional triangle cover and an optimal fractional triangle packing of , respectively. The result was generalized by Chapuy et al. [9] to the weighted version, which amounts to packing and covering triangles in multigraphs (obtained from by adding multiple edges). The authors [9] showed that and ; the arguments imply an LP-based 2-approximation algorithm for finding a minimum weighted triangle cover.

#### Our contributions.

Along a different line, we establish new sufficient conditions for validity of Tuza’s conjecture by comparing the triangle packing number, the number of triangles and the number of edges. Given a graph , we use is a triangle in to denote the set consisting of the (edge sets of) triangles in . Without loss of generality, we focus on the graphs in which every edge is contained in some triangle. These graphs are called irreducible.

###### Theorem 1.2.

Let be an irreducible graph. Then a triangle cover of with cardinality at most can be found in polynomial time, which implies , if one of the following conditions is satisfied: (i) , (ii) , (iii) .

The primary idea behind the theorem is simple: any one of conditions (i) – (iii) allows us to remove at most edges from to make the resulting graph satisfy ; the removed edges and the edges in a minimum triangle cover of form a triangle cover of with size at most . The idea is realized by establishing new results on linear 3-uniform hypergraphs (see Section 2); the most important one states that such a hypergraphs could be made acyclic by removing a number of vertices that is no more than a third of the number of its edges. A key observation here is that hypergraph is linear and 3-uniform.

To show the qualities of conditions (i) – (iii) in Theorem 1.2, we obtain the following result which complements to the constants , and 2 in these conditions with , and , respectively.

###### Theorem 1.3.

Tuza’s conjecture holds for every graph if there exists some real such that Tuza’s conjecture holds for every irreducible graph satisfying one of the following properties: (i’) , (ii’) , (iii’) .

We also investigate Tuza’s conjecture on classical Erdős-Rényi random graph , and prove that provided and .

It is worthwhile pointing out that strengthening Theorem 1.2, our arguments actually establish stronger results for linear 3-uniform hypergraphs (see Theorem 4.1).

The rest of paper is organized as follows. Section 2 proves theoretical and algorithmic results on linear 3-uniform hypergraphs concerning feedback sets, which are main technical tools for establishing new sufficient conditions for Tuza’s conjecture in Section 3. Section 4 concludes the paper with extensions and future research directions.

## 2 Hypergraphs

This section develops hypergraph tools for studying Tuza’s conjecture. The theoretical and algorithmic results are of interest in their own right.

Let be a hypergraph with vertex set and edge set . For convenience, we use to denote the number of edges in . If hypergraph satisfies and , we call a sub-hypergraph of , and write . For each , the degree is the number of edges in that contain . We say is an isolated vertex of if . Let be a positive integer, hypergraph is called -regular if for each , and -uniform if for each . Hypergraph is linear if for any pair of distinct edges .

A vertex-edge alternating sequence of is called a path (of length ) between and if are distinct, are distinct, and for each . We consider each vertex of as a path of length 0. Hypergraph is said to be connected if there is a path between any pair of distinct vertices in . A maximal connected sub-hypergraph of is called a component of . Obviously, is connected if and only if it has only one component.

A vertex-edge alternating sequence , where , is called a cycle (of length ) if are distinct, are distinct, and for each , where . We consider the cycle as a sub-hypergraph of with vertex set and edge set . For any (resp. ), we write for the sub-hypergraph of obtained from by deleting all vertices in and all edges incident with some vertices in (resp. deleting all edges in and keeping vertices). If is a singleton set , we write instead of . For any , the hypergraph is often written as , and as if .

A vertex (resp. edge) subset of is called a feedback vertex set or FVS (resp. feedback edge set or FES) of if it intersects the vertex (resp. edge) set of every cycle of . A vertex subset of is called a transversal of if it intersects every edge of . Let , and denote, respectively, the minimum cardinalities of a FVS, a FES, and a transversal of . A matching of is an nonempty set of pairwise disjoint edges of . Let denote the maximum cardinality of a matching of . It is easy to see that , and . Our discussion will frequently use the trivial observation that if no cycle of contains any element of some subset of , then and have the same set of FVS’s, and . The following theorem is one of main contributions of this paper.

###### Theorem 2.1.

Let be a linear -uniform hypergraph. Then .

###### Proof.

Suppose that the theorem failed. We take a counterexample with such that is as small as possible. Obviously . Without loss of generality, we can assume that has no isolated vertices. Since is linear, any cycle in is of length at least 3.

If there exists which does not belong to any cycle of , then . The minimality of implies , giving , a contradiction. So we have

• Every edge in is contained in some cycle of .

If there exists with , then , where the first inequality is due to the minimality of . Given a minimum FVS of , it is clear that is a FVS of with size , a contradiction to . So we have

• for all .

Suppose that there exists with . Let be the unique edge that contains . Recall from (1) that is contained in a cycle , where . By (2), we have for all . In particular implies , and in turn enforces . Let be a minimum FVS of . It follows from (2) that

 H∖v3⊆H∖{e2,e3}=H′⊕e1,

and in , edge intersects at most one other edge, and therefore is not contained by any cycle. Thus is a FVS of , and hence a FVS of , implying that is a FVS of . We deduce that . Therefore shows a contradiction to the minimality of . Hence the vertices of all have degree at least 2, which together with (2) gives

• is -regular.

Let be a shortest cycle in , where . For each , suppose that , where .

Because is a shortest cycle, for each pair of distinct indices , we have if and only if and are not adjacent in , i.e., . This fact along with the linearity of says that are distinct. By (3), each is contained in a unique edge , . We distinguish among three cases depending on the values of . In each case, we construct a proper sub-hypergraph of with and which shows a contradiction to the minimality of .

#### Case 1. k≡0(mod3):

Let be a minimum FVS of . Setting and , it follows from (3) that

 H∖V∗⊆(H∖Ec)⊕E∗=H′⊕E∗,

and in , each edge in intersects exactly one other edge, and therefore is not contained by any cycle. Thus is also acyclic, so is , saying that is a FVS of . We deduce that . Therefore shows a contradiction.

#### Case 2. k≡1(mod3):

Consider the case where or . Relabeling the vertices and edges if necessary, we may assume without loss of generality that . Let be a minimum FVS of . Set , if and , otherwise. In any case we have and

 H∖({u1,u3}∪V∗)⊆(H∖(Ec∪{f1,f3}))⊕({e2,e4}∪E∗)=H′⊕({e2,e4}∪E∗).

Note from (3) that in , each edge in can intersect at most one other edge, and therefore is not contained by any cycle. Thus is also acyclic, so is . Thus is a FVS of , and . This gives , a contradiction.

Consider the case where and . As are distinct and , we have . Observe that is a cycle in of length 4. The minimality of enforces . Therefore consist of 6 distinct edges. Let be a minimum FVS of . It follows from (3) that

 H∖{u2,u4}⊆(H∖(Ec∪{f1,f2}))⊕{e1,e3,f1}=H′⊕{e1,e3,f1}.

In , both and intersect only one other edge, which is , and any cycle through must contain or . It follows that none of is contained by a cycle of . Thus is acyclic, so is , saying that is a FVS of . Hence . In turn shows a contradiction.

#### Case 3. k≡2(mod3):

Let be a minimum FVS of . Setting and , we have and

 H∖({u1}∪V∗)⊆(H∖(Ec∪{f1}))⊕E∗=H′⊕E∗

In , each edge in intersects at most one other edge, and therefore is not contained by any cycle. Thus is acyclic, so is . Hence is a FVS of , yielding and a contradiction .

The combination of the above three cases complete the proof. ∎

We remark that the upper bound in Theorem 2.1 is best possible. See Figure 1 for illustrations of five 3-uniform linear hypergraphs attaining the upper bound. It is easy to prove that the maximum degree of every extremal hypergraph (those with ) is at most three. It would be interesting to characterize all extremal hypergraphs for Theorem 2.1.

The proof of Theorem 2.1 actually gives a recursive combinatorial algorithm for finding in polynomial time a FVS of size at most on a linear 3-uniform hypergraph .

Note that Algorithm 1 never visits isolated vertices (it only scans along the edges of the current hypergraph). The number of iterations performed by the algorithm is upper bounded by . Since is 3-uniform, the condition in any step is checkable in time. Any cycle in Step 7 or Step 9 can be found in time.111The shortest path between any pair of vertices can be find in time using breadth first search. A shortest cycle can be find by checking all possibilities. Thus Algorithm 1 runs in time.

###### Corollary 2.2.

Given any linear 3-uniform hypergraph , Algorithm 1 finds in time a FVS of with size at most .∎

###### Lemma 2.3.

If is a connected linear -uniform hypergraph without cycles, then .

###### Proof.

We prove by induction on . The base case where is trivial. Inductively, we assume that and the lemma holds for all connected acyclic linear 3-uniform hypergraph of edges fewer than . Take arbitrary . Since is connected, acyclic and 3-uniform, contains exactly three components , . Note that for each , hypergraph with is connected, linear, 3-uniform and acyclic. By the induction hypothesis, we have for . It follows that . ∎

Given any hypergraph , we can easily find a minimal (not necessarily minimum) FES in time: Go through the edges of the trivial FES in any order, and remove the edge from the FES immediately if the edge is redundant. The redundancy test can be implemented using Depth First Search.

###### Lemma 2.4.

Let be a linear -uniform hypergraph with components. If is a minimal FES of , then . In particular, .

###### Proof.

Suppose that contains exactly components , . It follows from Lemma 2.3 that for each . Thus , which means . To establish the lemma, it suffices to prove .

In case of , we have and . In case of , suppose that . Because is a minimal FES of , for each , there is a cycle in such that , and is a path in connecting two of the three vertices in . Considering being obtained from be removing sequentially, for , since , the presence of path implies that the removal of can create at most one more component. Therefore we have as desired. ∎

Given a hypergraph with vertices and edges, let be the incidence matrix. From , we may construct a bipartite graph with bipartition such that there is an edge of between and if and only if in .

Suppose that is acyclic. It is easy to see that is acyclic. Thus falls within the class of restricted totally unimodular (RTUM) matrices defined by Yannakakis [10]. As the name indicates, RTUM matrices are all totally unimodular. Hence the total unimodularity and LP duality give the well-known result [11] that . Moreover, since is RTUM, both a minimum transversal and a maximum matching of can be found in time using Yanakakis’s combinatorial algorithm [10] based on the current best combinatorial algorithms for the -matching problem and the maximum weighted independent set problem on a bipartite mulitgraph with vertices and edges, where the bipartite -matching problem can be solved with the minimum-cost flow algorithm in time (see Section 21.5 and Page 356 of [12]) and the maximum weighted independent set problem can be solved with maximum flow algorithm in time (See Pages 300-301 of [10]).

###### Theorem 2.5 ([11, 10]).

Let be a hypergraph with non-isolated vertices and edges. If has no cycle, then , and a minimum transversal and a maximum matching of can be found in time.∎

## 3 Triangle packing and covering

This section establish several new sufficient conditions for Conjecture 1.1 as well as their algorithmic implications on finding minimum triangle covers. Section 3.1 deals with graphs of high triangle packing numbers. Section 3.2 investigates irreducible graphs with many edges. Section 3.3 discusses Erdős-Rényi graphs with high densities.

To each graph , we associate a hypergraph , referred to as triangle hypergraph of , such that the vertices and edges of are the edges and triangles of , respectively. Since is simple, it is easy to see that is -uniform and linear, and . Note that , and if is irreducible, i.e., . Note that the number of non-isolated vertices of is upper bounded by .

### 3.1 Graphs with many edge-disjoint triangles

We investigate Tuza’s conjecture for graphs with large packing numbers, which are firstly compared with the number of triangles, and then with the number of edges.

###### Theorem 3.1.

If graph and real number satisfy , then a triangle cover of with size at most can be found in time, which implies .

###### Proof.

We consider the triangle hypergraph of which is 3-uniform and linear. By Corollary 2.2, we can find in time a FVS of with . Since , it follows that . As is acyclic, Theorem 2.5 enables us to find in time a minimum transversal of such that . We observe that and is triangle-free. Hence is a triangle cover of with size

 |S∪R|≤ν(HG)3c+ν(HG∖S)≤3c+13cν(HG)=3c+13cνt(G),

which proves the theorem. ∎

The special case of in the above theorem gives the following result providing a new sufficient condition for Tuza’s conjecture.

###### Corollary 3.2.

If graph satisfies , then .∎

The condition in Corollary 3.2 applies, in some sense, only to the class of large scale sparse graphs (which, e.g., does not include complete graphs on four or more vertices). The mapping from the real number in the condition to the coefficient in the conclusion of Theorem 3.1 shows the trade-off between conditions and conclusions. As in Corollary 3.2, maps to hitting the boundary of Tuza’s conjecture. It remains to study graphs with . The next theorem (Theorem 3.3) tells us that actually we only need to take care of graphs with


text:
# How to end the proof

1. Oct 13, 2008

### soul

Hi eveyone,

I was trying to prove that for the vector spaces, there is a unique vector that satisfy "u + 0 = u" and I used contradiction technique. The last point that I reached is $$u + 0_1 = u + 0_2$$. However, I don't know whether I can say $$0_1 = 0_2$$ after this statement or there are some other operations that I must do (like this statement needs a proof as well?).

Thank you.

Last edited: Oct 13, 2008
2. Oct 13, 2008

### Defennder

??? Why do you need to prove that? Isn't that an axiom that every vector space has to satisfy? Namely that every vector space has a unique zero vector? What axioms do you start off with?

You can "prove" this by noting that along with your last step, -u also exists in the same vector space.

3. Oct 13, 2008

### soul

Sorry, I guess I wrote my question wrong. I was trying to prove there is a unique identitiy element in summation and what I did is to select two different vectors and at the end of it, to show they are the same. I used the axiom in the question.

4. Oct 13, 2008

### HallsofIvy

Staff Emeritus
Uniqueness of the identity is an axiom in groups but can be proved in a vector space.

5. Oct 13, 2008

### d_leet

Is this true? Almost every group theory book I have looked at proves the uniqueness of the identity as a theorem.

6. Oct 13, 2008

### JasonRox

The axioms say there must exist a zero vector. It does not say it is unique or must be unique. You prove that it is unique if there exists such a vector.

7. Oct 15, 2008

### Jang Jin Hong

It is impossible to reply. You do not said definition of the vector space, and do not said about preceding procedure.

format: plain


text:
# Degree of Jacobian of homogeneous polynomials

What is the degree of the Jacobian (as a polynomial) of 3 homogeneous polynomials in 3 variables of degrees say $m_1, m_2$ and $m_3$ ?

I don't know how to prove that it is independent. In my case the degrees are $2,6$ and $10$. I have tried with some example and I found that the degree is $15$ in this case.

• One idea would be to test the proposition that the answer (degree of the Jacobian) does not depend on the particular polynomials, but can be found from the limited information given, by checking a few cases. Have you tried this? – hardmath Jul 7 '16 at 22:52
• I don't know how to prove that it is independent. In my case the degrees are $2,6$ and $10$. I have tried with some example and I found that the degree is 15 in this case. – Karthik Jul 8 '16 at 9:20
• See my Answer, and note that $2+6+10-3 = 15$. – hardmath Jul 8 '16 at 11:43
• where is your answer ? – Karthik Jul 8 '16 at 16:53
• I realized I'd omitted treating the important case that the Jacobian might be identically zero, so I temporarily deleted the Answer while adding that material. It is back now. – hardmath Jul 8 '16 at 16:57

Having done an example or two should give you a feeling for what can be said about the degree of the Jacobian knowing only the homogeneous degrees of the three polynomials are $m_1,m_2,m_3$ in three variables (say) $x,y,z$.

The Jacobian is the determinant of the $3\times 3$ matrix of first partial derivatives of the three polynomials.

The first partial derivatives of a polynomial of homogeneous degree $m$ will be polynomials of homogeneous degree $m-1$. So in the first row of the $3\times 3$ matrix the partials have degree $m_1-1$, in the second row $m_2-1$, and in the third row $m_3-1$. The product of three polynomials of homogeneous degrees $m_1-1,m_2-1,m_3-1$ will be of homogeneous degree (their sum of degrees) $m_1+m_2+m_3-3$.

Collecting like terms, any signed sum of polynomials of homogeneous degree $m_1+m_2+m_3-3$ will again be of that form, unless it happens to be identically zero.

An example of this with three polynomials of homogeneous degrees $2,6,10$ resp. is $p_1 = x^2, p_2 = y^3 z^3, p_3 = x^4 y^3 z^3$. Their Jacobian is:

$$\mathbf{J} = \det \begin{bmatrix} 2x & 0 & 0 \\ 0 & 3y^2z^3 & 3y^3z^2 \\ 4x^3y^3z^3 & 3x^4y^2z^3 & 3x^4y^3z^3 \end{bmatrix}$$

A brief if tedious calculation (expanding by minors) shows that $\mathbf{J}\equiv 0$. This can be inferred from the functional relationship:

$$p_3 = p_1^2 p_2$$

which implies the polynomial system is not invertible (uniquely solvable for $x,y,z$) at any point in $\mathbb{R}^3$, and therefore vanishes at every point.

However if the Jacobian computed as above is nonzero, it will be homogeneous of degree $m_1+m_2+m_3-3$ because there exist nonzero terms of that degree.


text:
# Difference between revisions of "2018 AMC 12B Problems/Problem 23"

## Problem

Ajay is standing at point $A$ near Pontianak, Indonesia, $0^\circ$ latitude and $110^\circ \text{ E}$ longitude. Billy is standing at point $B$ near Big Baldy Mountain, Idaho, USA, $45^\circ \text{ N}$ latitude and $115^\circ \text{ W}$ longitude. Assume that Earth is a perfect sphere with center $C$. What is the degree measure of $\angle ACB$?

$$\textbf{(A) }105 \qquad \textbf{(B) }112\frac{1}{2} \qquad \textbf{(C) }120 \qquad \textbf{(D) }135 \qquad \textbf{(E) }150 \qquad$$

## Solution

Suppose that Earth is a unit sphere with center $(0,0,0).$ We can let $$A=(1,0,0), B=\left(-\frac{1}{2},\frac{1}{2},\frac{\sqrt 2}{2}\right).$$The angle $\theta$ between these two vectors satisfies $\cos\theta=A\cdot B=-\frac{1}{2},$ yielding $\theta=120^{\circ},$ or $\boxed{\textbf{C}}.$

Note (not by author): Alternatively, to find the angle without dot products, one may compute the distance from $A$ to $B$ as

$\sqrt{\left(\frac{3}{2}\right)^2+\left(\frac{1}{2}\right)^2+\left(\frac{\sqrt{2}}{2}\right)^2}=\sqrt{3}$.

From the Law of Cosines, $3=1^2+1^2-2\cos{\theta}$, so $\cos{\theta}=-\frac{1}{2},$ from which the desired conclusion follows.


text:
# Ex.13.3 Q4 Surface Areas and Volumes Solution - NCERT Maths Class 10

Go back to  'Ex.13.3'

## Question

A well of diameter $$3\,\rm{m}$$ is dug $$14\,\rm{m}$$ deep. The earth taken out of it has been spread evenly all around it in the shape of a circular ring of width $$4\,\rm{m}$$ to form an embankment. Find the height of the embankment.

Video Solution
Surface Areas And Volumes
Ex 13.3 | Question 4

## Text Solution

What is known?

Depth of the well is $$14\rm{m}$$ and diameter is $$3\rm{m}$$. Width of the circular ring of the embankment is $$4\rm{m}$$.

What is unknown?

The height of the embankment.

Reasoning:

Draw a figure to visualize the shapes better

From the figure, it can be observed that the shape of the well will be cylindrical, and earth evenly spread out to form an embankment around the well in a circular ring will be in a cylindrical shape (Hollow cylinder) having outer and inner radius.

Volume of the earth taken out from well $$=$$ Volume of the earth used to form embankment

Hence, Volume of the cylindrical well $$=$$ Volume of the hollow cylindrical embankment

We will find the volume of the hollow cylindrical embankment by subtracting volume of inner cylinder from volume of the outer cylinder.

Volume of the cylinder $$= \pi {r^2}h$$

where $$r$$ and $$h$$ are the radius and height of the cylinder respectively.

Steps:

Depth of the cylindrical well,$${h_1} = 14 \rm m$$

Radius of the cylindrical well,\begin{align}r = \frac{3}{2} \rm m = 1.5m\end{align}

Width of embankment $$= 20 \rm m$$

Inner radius of the embankment,\begin{align}r = \frac{3}{2} \rm m\end{align}

Outer radius of the embankment, R $$=$$ Inner radius $$+$$ Width

\begin{align}R &= 1.5 \rm m + 4m\\&= 5.5 \rm m\end{align}

Let the height of embankment be $$h$$

Volume of the cylindrical well $$=$$ Volume of the hollow cylindrical embankment

\begin{align}\pi {r^2}{h_1} &= \pi {R^2}h - \pi {r^2}h\\\pi {r^2}{h_1} &= \pi h\left( {{R^2} - {r^2}} \right)\\{r^2}{h_1} &= h\left( {R - r} \right)\left( {R + r} \right)\\h &= \frac{{{r^2}{h_1}}}{{\left( {R - r} \right)\left( {R + r} \right)}}\\&= \frac{{{{\left( {1.5 \rm m} \right)}^2} \times 14 \rm m}}{{ \begin{bmatrix}\left( {5.5\rm m - 1.5m} \right) \\ \left( {5.5 \rm m + 1.5} \right) \end{bmatrix}}}\\&= \frac{{2.25\rm {m^2} \times 14m}}{{4 \rm m \times 7m}}\\&= 1.125 \rm m\end{align}

Therefore, the height of the embankment will be $$1.125\rm{ m.}$$

Learn from the best math teachers and top your exams

• Live one on one classroom and doubt clearing
• Practice worksheets in and after class for conceptual clarity
• Personalized curriculum to keep up with school


text:
# Advanced lane finding model

The model will consist of two parallel CNNs, each of which end with a dense 100-unit layer, which we will then concatenate and pass through three additional dense layers, and end with two linear activations. The model should have about 6.5 million parameters, which take up about 2GB of VRAM, so we should be able to run it on our Jetson Nano with half that much RAM to spare. :)

## The idea of teaching a vehicle to drive autonomously

Now I know that a whole separate (and rather big) CNN is an overkill for the thresholded binary image, but the main reason why I'm currently doing it like this is to test if its possible to have multiple specialized parts of the architecture all siphon in to a smaller final part (the last n dense layers) in order for the car to make a decision where to steer and how much to throttle, which is more or less how you do everything while you're in a car, parking, driving, you just combine multiple inputs, e.g.:

• Checking your mirrors and dead angle to make sure you're safe to do a maneuver - collision avoidance, object recognition and tracking
• Recognizing a sign that says what exit you should take in order to get to your destination
• Actually knowing where you are with respect to that exit and by what path can you get to it - path planning, localization
• Actually give the appropriate steering and throttle to actually perform the maneuver

So no matter what we're doing in a car, be it parking, changing lanes or driving to a destination, all we can really do to control the car is turn the steering wheel and control its speed (assuming no gear shifting, e.g. an electric car 😋), we're just taking in the input from our surroundings, mostly using our eyes, which we analyze through a series of specialized procedures which ultimately lead us to control our car based on the decisions we've made, in order to perform a maneuver.

So what I wanted to do is to have a series of specialized parts in the net, which we could even call smaller subnets, which would take the input images and extract highly specific data from it, using (relatively) specialized procedures, which we would then plug into the final layer, along with the first convolutional network that uses the raw input image, which should give the final part of the network enough context about the world and enough information in order to appropriately control the RC.

It would look something like this:

I was playing around with the idea in my mind when I saw Andrej Karpathy's talk on PyTorch at Tesla, where he explained their use of HydraNets. In a nutshell, because they have a 1000 (!) distinct output tensors (predictions), and all of them have to know a ton of context and details about the scene, they use a shared backbone, like this (screenshot taken from YouTube: PyTorch at Tesla:

They actually have 48 networks that output a total of 1000 predictions, which is insane to do in real-time (on 1000x1000 images and 8 cameras) while being accurate enough to actually drive living humans on real roads. Though, they do have some pretty sweet custom hardware (FSD2), unlike our Jetson Nanos 😢.

Now, it obviously makes much more sense to do what Tesla did, to have a shared backbone since a lot of the information that the backbone extracts from the input images can be applied to all of the specialized tasks, so you don't have to learn them all over again for each and every one of them.

But I figured, what the heck, I'd try my idea out, which I did, since the main reason for doing this is to actually learn to apply ML/DL to something I could actually see drive around my backyard, and when we teach the car to do behaviours like lane changing in the next chapter, you'll see that it actually works!

This is what it looks like in action:

Let's implement it.

### Creating a Keras model

First off, we'll create a Keras model in the donkeycar/parts folder. I'll be calling it OriModel.

from donkeycar.parts.keras import KerasPilot

from tensorflow.python.keras.models import Model, Sequential
from tensorflow.python.keras.layers import Input, Dense, Activation, Dropout, Flatten, Conv2D
from tensorflow.python.keras.layers.merge import Concatenate

import cv2
import numpy as np

We'll be inheriting the base KerasPilot class for Donkey, the model will be a sequential one and among others it will use dense, 2D convolutional layers and the concatenation layer.

We'll also need OpenCV and Numpy for our image preprocessing.

We'll start by inheriting the base class and implementing the constructor and compile methods:

class OriModel(KerasPilot):
'''
Custom model that takes an input image and feeds it and a preprocessed version of it to the model.
The preprocessing converts the image to HSL color space, extracts the S channel and thresholds it.
The thresholded S channel is passed to the model to help find lane lines easier.
'''
def __init__(self, model=None, input_shape=(180, 320, 3), *args, **kwargs):
super(OriModel, self).__init__(*args, **kwargs)
self.model = oriModel(inputShape=input_shape)
self.compile()

def compile(self):
self.model.compile(optimizer=self.optimizer,
loss='mse')

We'll want to preprocess images at runtime, so we can use it during inference, so we'll implement the run method accordingly:

def run(self, inputImage):
# Preprocesses the input image for easier lane detection
extractedLaneInput = self.processImage(inputImage)
# Reshapes to (1, height, width, channels)
extractedLaneInput = extractedLaneInput.reshape((1,) + extractedLaneInput.shape)
inputImage = inputImage.reshape((1,) + inputImage.shape)
# Predicts the output steering and throttle
steering, throttle = self.model.predict([inputImage, extractedLaneInput])
print("Throttle: %f, Steering: %f" % (throttle[0][0], steering[0][0]))
return steering[0][0], throttle[0][0]

We'll use the code we wrote in the previous chapter and unify it in a couple helper methods:

def warpImage(self, image):
# Define the region of the image we're interested in transforming
regionOfInterest = np.float32(
[[0,  180],  # Bottom left
[112.5, 87.5], # Top left
[200, 87.5], # Top right
[307.5, 180]]) # Bottom right

# Define the destination coordinates for the perspective transform
newPerspective = np.float32(
[[80,  180],  # Bottom left
[80,    0.25],  # Top left
[230,   0.25],  # Top right
[230, 180]]) # Bottom right
# Compute the matrix that transforms the perspective
transformMatrix = cv2.getPerspectiveTransform(regionOfInterest, newPerspective)
# Warp the perspective - image.shape[:2] takes the height, width, [::-1] inverses it to width, height
warpedImage = cv2.warpPerspective(image, transformMatrix, image.shape[:2][::-1], flags=cv2.INTER_LINEAR)
return warpedImage

def extractLaneLinesFromSChannel(self, warpedImage):
# Convert to HSL
hslImage = cv2.cvtColor(warpedImage, cv2.COLOR_BGR2HLS)
# Split the image into three variables by the channels
hChannel, lChannel, sChannel = cv2.split(hslImage)
# Threshold the S channel image to select only the lines
lowerThreshold = 65
higherThreshold = 255
# Threshold the image, keeping only the pixels/values that are between lower and higher threshold
returnValue, binaryThresholdedImage = cv2.threshold(sChannel,lowerThreshold,higherThreshold,cv2.THRESH_BINARY)
# Since this is a binary image, we'll convert it to a 3-channel image so OpenCV can use it
thresholdedImage = cv2.cvtColor(binaryThresholdedImage, cv2.COLOR_GRAY2RGB)
return thresholdedImage

def processImage(self, image):
warpedImage = self.warpImage(image)
# We'll normalize it just to make sure it's between 0-255 before thresholding
warpedImage = cv2.normalize(warpedImage,None,0,255,cv2.NORM_MINMAX,cv2.CV_8U)
thresholdedImage = self.extractLaneLinesFromSChannel(warpedImage)
one_byte_scale = 1.0 / 255.0
# To make sure it's between 0-1 for the model
return np.array(thresholdedImage).astype(np.float32) * one_byte_scale

And now to the architecture/model itself. First, let's define the inputs and the dropout rate:

def oriModel(inputShape, numberOfBehaviourInputs):

# Dropout rate
keep_prob = 0.9
rate = 1 - keep_prob

# Input layers
imageInput = Input(shape=inputShape, name='imageInput')
laneInput = Input(shape=inputShape, name='laneInput')
behaviourInput = Input(shape=(numberOfBehaviourInputs,), name="behaviourInput")

Now let's define the upper CNN, which takes in the raw image as its input:

# Input image convnet
x = imageInput
x = Conv2D(24, (5,5), strides=(2,2), name="Conv2D_imageInput_1")(x)
x = LeakyReLU()(x)
x = Dropout(rate)(x)
x = Conv2D(32, (5,5), strides=(2,2), name="Conv2D_imageInput_2")(x)
x = LeakyReLU()(x)
x = Dropout(rate)(x)
x = Conv2D(64, (5,5), strides=(2,2), name="Conv2D_imageInput_3")(x)
x = LeakyReLU()(x)
x = Dropout(rate)(x)
x = Conv2D(64, (3,3), strides=(1,1), name="Conv2D_imageInput_4")(x)
x = LeakyReLU()(x)
x = Dropout(rate)(x)
x = Conv2D(64, (3,3), strides=(1,1), name="Conv2D_imageInput_5")(x)
x = LeakyReLU()(x)
x = Dropout(rate)(x)
x = Flatten(name="flattenedx")(x)
x = Dense(100)(x)
x = Dropout(rate)(x)

I'll explain why I'm using LeakyReLU in a moment. Let's define the bottom CNN which takes in the thresholded lane image as its input:

# Preprocessed lane image input convnet
y = laneInput
y = Conv2D(24, (5,5), strides=(2,2), name="Conv2D_laneInput_1")(y)
y = LeakyReLU()(y)
y = Dropout(rate)(y)
y = Conv2D(32, (5,5), strides=(2,2), name="Conv2D_laneInput_2")(y)
y = LeakyReLU()(y)
y = Dropout(rate)(y)
y = Conv2D(64, (5,5), strides=(2,2), name="Conv2D_laneInput_3")(y)
y = LeakyReLU()(y)
y = Dropout(rate)(y)
y = Conv2D(64, (3,3), strides=(1,1), name="Conv2D_laneInput_4")(y)
y = LeakyReLU()(y)
y = Dropout(rate)(y)
y = Conv2D(64, (3,3), strides=(1,1), name="Conv2D_laneInput_5")(y)
y = LeakyReLU()(y)
y = Flatten(name="flattenedy")(y)
y = Dense(100)(y)
y = Dropout(rate)(y)

Now we have to concatenate the two networks and feed them into the last three dense layers:

# Concatenated final convnet
c = Concatenate(axis=1)([x, y])
c = Dense(100, activation='relu')(c)
c = Dense(50, activation='relu')(c)

And finally, we'll define the output and return the model:

# Output layers
steering_out = Dense(1, activation='linear', name='steering_out')(o)
throttle_out = Dense(1, activation='linear', name='throttle_out')(o)
model = Model(inputs=[imageInput, laneInput, behaviourInput], outputs=[steering_out, throttle_out])

return model

## Why LeakyReLU

As every model, this one began as one thing and ended up a whole different thing in terms of hyperparameters and the architecture. I'll explain that in much more detail in the next chapter. But one thing that happened to me while training the above model using ReLU as the activation function for the convolutional layers was dying ReLU(s).

First, let's remember how the ReLU (Rectified Linear Unit) function is defined: $$f(x) \begin{cases} x & \text{when x=>0}\\ 0 & \text{when x<0} \end{cases}$$ This is what it looks like when plotted:

You can see that any negative input will result in a 0 activation for the ReLU function.

Now imagine we get a large negative value that gets input to our unit that uses the ReLU activation function. It will cause the unit weights to update in a way that will prevent it to ever be activated again.

This is a known disadvantage of ReLU, and there are even papers written on this topic alone 1. Stanford's course CS231n states that: you can find that as much as 40% of your network can be “dead” .

In my case, the neural network was just outputting the same throttle and steering values for every input. And since it had a lot of layers, I knew it should be learning at least something, and after removing the small (10%) dropout rate I've implemented, and after it still hasn't changed, I realised that many of the convolutional units weren't really outputting anything, which caused the rest of the network to just have the same output over and over again.

The fix was obviously to use either LeakyReLU or PReLU or any other activation function made specifically to overcome this advantage of ReLUs, while still preserving it's linear non-saturating form.

Why not PReLU? Because I wanted to try something simple before having an additional parameter to train, which I'd get by using PReLUs, and after trying out LeakyReLU the model trained just fine, with the loss being close to 0.001 (using MSE as the loss function).

Here's the definition of LeakyReLU $$f(x) \begin{cases} x & \text{when x=>0}\\ \alpha \cdot x & \text{when x<0} \end{cases}$$ The default alpha in Keras is 0.3. Here's a plot of LeakyReLU with $\alpha = 0.3$:

And here's a plot when $\alpha = 0.03$:

You can choose whichever $\alpha$ value you'd like. This will allow the unit to activate even if the value is negative.

Speaking of choosing $\alpha$, the main idea behind PReLU is to make it a parameter which the network will learn. You can read about PReLUs in this paper they were first proposed by He et al. or you can take a look at the Keras implementation here.

## Training the network

I've trained the network using about 10k records made on the randomly generated track, and left the network to train for 12 epochs which took 21m 45s on my RTX 2060. The final validation loss was 0.003665.

Here is a graph showing a plot of the training loss vs the validation loss:

Here is the training loss plot with the two separate outputs plotted:

Here is the validation loss plot with the two separate outputs plotted:


text:
News Center

# EMT Decomposition

The actual problem with Ji's decomposition is that the separation of the EMT into traceless and trace parts is not inconsequential for the physical interpretation of the individual contributions. Footnote 6 Namely, although (T^{00}), (bar{T}^{00}) and (hat{T}^{00}) all have the dimension of energy densities, they actually correspond ...

[email protected]

## News Detail

• The 5 Signs of Irreversible Death - Verywell Health

When decomposition is a sign of death, it means that the entire body has begun to decompose, that the person is not breathing, and the heart is not beating.

Get Price
• Disposition of the Deceased: How to determine patient

Mar 01, 2010LAFD established a policy that allows EMTs or paramedics to transport decedents directly to the coroner’s office in two situations: The patient is

Get Price
• Revisiting the proton mass decomposition

decomposition. This feature also applies to the operator associated with the EMT trace anomaly. Related to that point, we argue that any potential decomposition of the proton mass can at most have two independent terms. This is due to the fact that, in the forward limit, the EMT has two independent form factors only, as has already been

Get Price
• Aitken Schwarz heterogeneous Domain Decomposition for EMT

Schwarz heterogeneous domain decomposition method (DDM) is used to co-simulate an RLC electrical circuit . A part of the domain is modeled with Electro-Magnetic Transients (EMT) modeling and the other part with dynamic phasor (TS) modeling .

Get Price
• Compensated vs. decompensated shock - EMS, EMTs Paramedics

EMS 101 articles are intended to educate a non-emergency medical services audience about the emergency medical services profession. These articles are written by

Get Price
• EMT Chapter 3 Flashcards | Quizlet

decomposition of the bodys tissues. The EMTs scope of practice within his or her local response area is defined by the: medical director. To help protect patients, EMS agencies are required to have: a privacy officer to answer questions. When is forcible restraint permitted?

Get Price
• The Stages Of Human Decomposition | Aftermath Services

The first stage of human decomposition is called autolysis, or self-digestion, and begins immediately after death. As soon as blood circulation and respiration stop, the body has no way of getting oxygen or removing wastes. Excess carbon dioxide causes an acidic environment, causing membranes in

Get Price
• EMT International - Processing Equipment for Digital

EMTs Chameleon line of finishing equipment offers a complete range of modular dynamic web finishing solutions. Tight or slack web management, in-line, near-line or off-line, the Chameleon adapts to your specific web processing and finishing needs. More About Finishing Solutions.

Get Price
• Decomposition Book - 100% Recycled Notebooks - Made in USA

Makers of the Decomposition Book - Over 100 styles in stock - Made with 100% Recycled Paper - Printed with Soy Ink - Made in the USA

Get Price
• Decomposition of Organic Matter - an overview

Decomposition of organic matter involves four component processes: photo-oxidation, leaching, comminution, and mineralization. Arthropods are key factors

Get Price
• Aitken-Schwarz heterogeneous Domain Decomposition for EMT

Feb 04, 2021Abstract: In this paper, a Schwarz heterogeneous domain decomposition method (DDM) is used to co-simulate an RLC electrical circuit where a part of the domain is modeled with Electro-Magnetic Transients (EMT) modeling and the other part with dynamic phasor (TS) modeling. Domain partitioning is not based on cutting at transmission lines which introduces a

Get Price
• Decomposition: What is there to know about it?

May 11, 2018Decomposition is a phenomenon through which the complex organic components of a previously living organism gradually separate into ever simpler elements. In the words of forensic scientist M. Lee...

Get Price
• Introduction to the Empirical Mode Decomposition Method

Jul 18, 2012This article serves to familiarize the reader with the empirical mode decomposition (EMD) method. It is the fundamental part of the Hilbert–Huang transform and is intended for analyzing data from nonstationary and nonlinear processes. This article also features a possible software implementation of this method along with a brief consideration of its peculiarities and gives some simple

Get Price
• EMS and the septic patient

Webster’s defines septic as relating to purification, or the decomposition of organic matter. While decomposition is essential in the grand scheme of things, it is not entirely desirable in a...

Get Price
• Emergency Medical Services | City of Sioux City website

The EMS Division is supervised by an EMS Director with a line staff of three officers, a force of 24 Emergency Medical Technicians, a Compliance Officer and a Division Training Officer. PRIVACY PRACTICES. Your health information has always been an important priority of Sioux City Fire Rescue. Our employees respect the confidential nature of

Get Price

The actual problem with Ji’s decomposition is that the separation of the EMT into traceless and trace parts is not inconsequential for the physical interpretation of the individual contributions. Footnote 6 Namely, although $$T^{00}$$ , $$\bar{T}^{00}$$ and $$\hat{T}^{00}$$ all have the dimension of energy densities, they actually correspond

Get Price
• Hahn decomposition theorem - Wikipedia

In mathematics, the Hahn decomposition theorem, named after the Austrian mathematician Hans Hahn, states that for any measurable space (,) and any signed measure defined on the -algebra , there exist two -measurable sets, and , of such that: ∪ = and ∩ = ∅. For every ∈ such that ⊆, one has () ≥, i.e., is a positive set for .; For every ∈ such that ⊆, one has () ≤, i.e., is a

Get Price
• Cholesky decomposition - Wikipedia

Inserting the decomposition into the original equality yields = ∗ = ∗ = ∗ ∗ = ∗. Setting = ∗ completes the proof.

Get Price
• Talk:Decomposition - Wikipedia

Chance Gearheart, EMT-IV. You could just as easily argue that animal decomposition should be under Animal Decomposition. I think the idea here is to give a balanced, perhaps brief account of each type of decomposition. Each type could then be elaborated in their own article. `Zozart.chat 07:21, 12

Get Price
• 814 - Determination of Death 20200330 - Signed

(EMT/ PARAMEDIC/MICN) SUBJECT: DETERMINATION / PRONOUNCEMENT REFERENCE NO. 814 OF DEATH IN THE FIELD EFFECTIVE: 10-10-80 PAGE 1 OF 7 REVISED: 03-30-20 SUPERSEDES: 07-01-19 APPROVED: Director, EMS Agency Medical Director, EMS Agency PURPOSE: This policy is intended to provide EMS personnel with parameters to determine

Get Price
• EMR Test 1 Review Flashcards - Questions and Answers | Quizlet

A. an EMS provider assesses a patient but fails to transport and later learns the patient died. B. a competent patient refuses treatment at the scene but later dies of a hidden injury or illness. C. an EMR transfers care of a critically injured patient to a certified EMT or paramedic.

Get Price
• PREHOSPITAL DEATH DETERMINATION

Clark County EMS personnel if any of the following obvious signs of death are present: a) Body decomposition b) Decapitation c) Transection of thorax (hemicorpectomy) d) Incineration OR if ALL four (4) presumptive signs of death AND AT LEAST one (1) conclusive sign of death are identified. 2.

Get Price
• Chapter 2. Organic matter decomposition and the soil food web

Soil organic matter. When plant residues are returned to the soil, various organic compounds undergo decomposition. Decomposition is a biological process that includes the physical breakdown and biochemical transformation of complex organic molecules of dead material into simpler organic and inorganic molecules (Juma, 1998).

Get Price
• Decompose | Definition of Decompose by Merriam-Webster

Decompose definition is - to separate into constituent parts or elements or into simpler compounds. How to use decompose in a sentence. Synonym Discussion of decompose.

Get Price
• NCL: Empirical Mode Decomposotion (EMD)

An overview of Empirical Mode Decomposition is provided by Lambert.A project website for the course ELEC 301 at Rice University. EMD (Empirical Mode Decomposition) is an adaptive time-space analysis method suitable for processing series that are non-stationary and non-linear. EMD performs operations that partition a series into modes (IMFs; Intrinsic Mode Functions) without leaving the time

Get Price
• Heat Of Decomposition | Definition of Heat Of

Heat of decomposition definition is - the heat of reaction resulting from the decomposition of a compound into its elements or into other neutral compounds; especially : the quantity involved in the decomposition of a mole.

Related News


text:
# How do you find the value of the discriminant and state the type of solutions given 4k^2+5k+4=-3k?

Oct 20, 2017

$\Delta = 0$
$1$ repeated root

#### Explanation:

rearrange the equation into the form $a {k}^{2} + b k + c = 0$:

$4 {k}^{2} + 5 k + 4 = - 3 k$
$4 {k}^{2} + 5 k + 3 k + 4 = 0$
$4 {k}^{2} + 8 k + 4 = 0$

divide both sides by $4$:
${k}^{2} + 2 k + 1 = 0$

$a {k}^{2} + b k + c = 0$
${k}^{2} + 2 k + 1 = 0$

$\therefore a = 1 , b = 2 , c = 1$

$\Delta$ (discriminant) $= \left({b}^{2} - 4 a c\right)$ for a quadratic equation

here, ${b}^{2} - 4 a c = {2}^{2} - \left(4 \cdot 1 \cdot 1\right)$
$= 4 - 4$
$= 0$

$0 = 0$
since $\Delta = 0 , k$ has $1$ repeated root.

on a graph:

the parabola only meets the $x$-axis once- there is only $1$ root.

through factorisation:

${k}^{2} + 2 k + 1 = 0$
$\left(k + 1\right) \left(k + 1\right) = 0$
solving for $k$, you get
'$k = - 1$ or $k = - 1$'

the number $- 1$ is repeated, giving the name 'repeated root'.


text:
# Raytracing and Raycasting with Signed Distance Functions

## August 15, 2022

Categories: Math Programming Graphics

I stumbled onto the concept of using signed distance functions (SDFs) to represent a three dimensional geometry almost by accident when looking up ways to generate 3D models (for 3D printers) programatically, as opposed to using traditional CAD software. Unlike more standard CAD processes for 3D printers, which tends to boil down to triangular meshes, SDFs are mathematical functions that can represent exact surface curvature. As I also have a background in physics-accurate optics I realized this property made SDFs ideal for high precision optical simulations, which is essentially the same thing as photo realistic rendering. It was immediately apparent with some quick googling that other people had previously explored the same ideas to great effect, but was interested enough that I got hooked, and decided to play around with writing my own rendering engine based on SDFs, and learn a bit along the way.

The sdfray renderer started as a few hundred lines of python code to find intersections of rays with an SDF. It evolved into a pure-Python CPU rendering framework, using Numpy for the math, and finally into a Python framework for generating and running GLSL shader code for. To help you understand what that means, I’ll dispense with the background knowledge first, then get into examples of the interesting bits.

## Signed Distance Functions (SDFs)

Signed distance functions (you may see me use field and function interchangeably here) define the surface, or boundary, of an object by where some mathematical function goes through zero. They also possess the property that the value of the function is either the minimum distance to the surface or the negative of that if “inside” the object.

In general, such a function can be quite complicated, but for certain basic shapes, there are concise mathematical forms. A unit sphere at the origin is the simplest $$S(\vec{p}) = \left|\vec{p}\right|^2 - 1 = x^2 + y^2 + z^2 - 1$$ where it is clear that the value is:

• $-1$ at the origin - negative because inside, and one because the surface is one unit away,
• $0$ at the surface - $x^2+y^2+z^2 = 1$ is the usual definition for a unit sphere,
• the shortest distance to the surface, otherwise.

Inigo Quilez put together a nice article and many other resources with SDF implementations and techniques, which is worth checking out. These functions are interesting from a representational perspective for several reasons that deserve some discussion in the following sections.

### Exact geometries

Most importantly to me, SDFs can represent a nonflat surface to arbitrary precision in a concise form, much unlike a triangular mesh that is popular in realtime computer graphics. This means that reflections and refraction won’t have to deal with flat surface approximations. It also means that for high detail one does not have to go to millions or billions of triangles on models, but rather define some function with sufficient detail. Because of this, signed distance functions have been used to study and display fractals, which have detail at all length scales.

### Simple operations

Of algorithmic interest, there are simple methods for performing boolean operations on SDFs. The simplicity stems from SDFs being minimum distance fields. The SDF union $U_{ab}(\vec{x})$ of two SDF $a(\vec{x})$ and $b(\vec{x})$ is simply the lesser of the two SDF at any point $$U_{ab}(\vec{x}) = \min(a(\vec{x}),b(\vec{x}))$$ which tautologically means the nearest of the two surfaces is the closest surface.

There’s also an intersection operation $I_{ab}(\vec{x})$ resulting in the overlap of $a$ and $b$. $$I_{ab}(\vec{x}) = \max(a(\vec{x}),b(\vec{x}))$$ which leverages the fact that SDFs are negative on the interior; the only remaining interior is where both interiors overlap, and the exterior is always the distance to the furthest surface.

Finally, the subtraction operation, to round out the constructive solid geometry, $S_{ab}(\vec{x})$ resulting in the boolean operation $a$ - $b$, or $a$ with $b$ removed. $$S_{ab}(\vec{x}) = \max(a(\vec{x}),-b(\vec{x}))$$ Here, the subtracting SDF is inverted, making its interior into exterior. The maximum, then, will always be the distance to $a$ on the exterior of $a$, but wherever $b$ overlaps $a$ becomes exterior, since $b$ was negated.

With these operations, and a sufficient collection of primitive shapes, in principle any geometry can be constructed. Unfortunately, these CSG operations require evaluating both primitive (or composite!) SDFs, and on top of that have some issues with the interiors. It is important to recall that this is not the only way to construct SDFs, and indeed techniques like solids of revolution can perform better. As may people have explored this, I’ve stuck with CSG solids for demonstration purposes.

### Fast ray intersection

Finally, and what inspired me to go further down the path of rendering, finding an intersection with a SDF geometry is a wholly different, and much faster, exercise than doing the same with triangular meshes. The latter is, of course, very simple, as one can directly calculate whether a ray intersects a triangle with well known formulas. The complexity comes with the sheer number of triangles one has to deal with, and the possibility that multiple triangles are intersected by the ray, but only one is visible.

For an SDF there is no general formula (though there are for specific cases) to calculate an intersection position. Instead, one can take advantage of the property that the value of the SDF is the minimum distance to a surface. There may not be a surface in the direction of the ray, but we know that the ray can be advanced by at least the value of the SDF without encountering any surface. Repeating this process will eventually result in either the value of the SDF approaching zero, meaning a surface has been encountered, or increasing forever, meaning there was no surface in the initial direction. This typically takes far fewer steps than there would be potential triangle intersections to calculate, making this potentially viable for real time raytracing or raycasting techniques. This, of course, relies on efficient evaluation of the SDF.

#### How much faster?

If the SDF is constructed from many operations on primitive shapes, single evaluations of the SDF could be many expensive floating point operations. The tipping point is probably somewhere around where the average number of steps necessary to find a surface, $N_{SDF}$, times the complexity of the SDF evaluation, $C_{SDF}$, approaches the number of triangles, $N_{TRI}$, times the complexity of calculating a triangle intersection, $C_{TRI}$. One could argue that $C_{SDF}$ is some primitive shape complexity, $\overline{C_{SDF}}$, times number of primitive shapes, $N_{PRI}$, and $N_{TRI}$ could be something like number of primitive shapes, $N_{PRI}$, times some average numer of triangles per shape, $\overline{N_{TRI}}$. With these made up variables, we favor SDF raytracing to triangle mesh raytracing when the following is true:

\begin{aligned} N_{SDF} C_{SDF} &< N_{TRI} C_{TRI} \\ N_{SDF} \overline{C_{SDF}} N_{PRI} &< N_{PRI} \overline{N_{TRI}} C_{TRI} \\ N_{SDF} \overline{C_{SDF}} &< \overline{N_{TRI}} C_{TRI} \end{aligned}

The complexity of intersecting a ray with one triangle is roughly the same order of magnitude as evaluating the SDF for one primitive shape. Both are pretty straightforward mathematical calculations. This means we an assume $\overline{C_{SDF}} \approx C_{TRI}$ leaving $$N_{SDF} < \overline{N_{TRI}}$$ or that the average number of steps in finding an intersection should be less than the agerage number of triagles for simple shapes for SDFs to be competitive. When curved surfaces are involved, and high precision is needed there, this is often the case.

## Raycasting and Raytracing

If you hold an empty picture frame in front of you, such tht some scene is contained within the frame, you have to look in particular directions from a particular location to see items withing the scene. In the same way, computer graphics are rendered by checking to see what color (and how bright) a particular part of the scene is, given a location and a direction. A location and a direction is a mathematical ray, and this checking of the scene color is the algorithm of raycasting, raytracing, or any number of techniques employed for creating computer generated images.

Typically this is an independent process for each pixel in an image; each pixel is cast as a ray to determin its color. The Python and GLSL code fragments for this can be found in sdfray’s rendering core. This proceeds according to the following rough outline:

### 1. Find an intersection

This is the stepping process where the SDF is evaluated at the point of a ray’s origin, and the value (minimum distance to a surface) is used to advance the ray until it encounters a surface. For some batch of rays with properties for origins p and directions d and an sdf, some python code to do this follows:

WORLD_RES = 1e-4
WORLD_MAX = 1e4
def next_surface(p,d,sdf):
alive = np.arange(len(p))
intersected = np.zeros(len(p),dtype=bool)
while len(alive) > 0:
sd = sdf(p[alive])
if np.any(m := (sd < WORLD_RES)): # hit something
intersected[m] = True
m = ~m
alive = alive[m]
sd = sd[m]
if np.any(m := L(p[alive]) > WORLD_MAX): # infinity
m = ~m
alive = alive[m]
sd = sd[m]
p[alive,:] += (rays.d[alive].T*np.abs(sd)).T # advance batch
return p,intersected

While the equivelant GLSL shader code would look something like:

float sdf(vec3 xyz) {
// Since we can't pass a function by reference...
}

const float WORLD_RES = 1e-4;
const float WORLD_MAX = 1e4;
bool next_surface(inout vec3 p, inout vec3 d) {
for (int i = 0; i < 2500; i++) {
float v = sdf(p);
if (v < WORLD_RES) {
return true;
} else if (v > WORLD_MAX) {
return false;
}
p += v*d;
}
return false;
}

There are some additional considerations for a more robust method that can deal with low precision floating point math, where one might slightly over or undershoot, which can be found in the final codebase.

### 2. Determine the surface properties

My earliests tests were some few-hundred line long pure-python renderers with a hardcoded SDF which assumed all surfaces had the same diffuse reflectivity. The only frill was a bit of shading for the angle of the surface relative to a light source. Moving to something more complicated required a lot of infrastructure to keep track of surface properties. Not only are there multiple properties at each point, but different points may have to different sets of properties.

On the python side, it was fairly easy to have each primitive be an SDF object that had associated properties. So when evaluating the SDF, one could simply query for the surface property at a point instead.

class SurfaceProp:
'''Defines properties of a surface'''

def __init__(self,color=A([1.0,1.0,1.0]),diffuse=0.8,specular=0.0,refractive_index=1.0,transmit=0.0,emittance=A([0.0,0.0,0.0])):
'''Most quantities are multipliers for effects. [0,1] is realistic, but not required
Refractive index is the usual way, where the speed of light in the medium is c/n
Default surface is 80% diffuse reflective'''
self.diffuse = diffuse
self.specular = specular
self.refractive_index = refractive_index
self.transmit = transmit
self.color = color
self.emittance = emittance

In the GLSL code one is not fortunate enough to have objects and associated methods, but one does at least have structs. The same properties can be represented as a struct, and another method sdf_prop constructed to re-evaluate the sdf for properties instead of distance.

struct Property {
float diffuse, specular, transmit, refractive_index;
vec3 color, emittance;
};

struct GeoInfo {
float sdf;
Property prop;
};

GeoInfo wrap(float sdf, Property prop) {
return GeoInfo(sdf,prop);
}

GeoInfo wrap(GeoInfo info, Property prop) {
return GeoInfo(info.sdf,prop);
}

Property sdf_prop(vec3 p) {
return wrap(/* SDF HERE */,Property(1.,0.,0.,0.,vec3(1.,1.,1.),vec3(0.,0.,0.)));
}

#### Surface Normals

All the surface properties depend in some way on the orientation of the surface, because this influences how light illuminates a surface. It is therefore critical to exctract the surface normal vector - a vector that is unit length and perpendicular to the surface at a point. The distance properties of SDFs make this straightfoward: the gradient of the SDF $a$, or $\vec{\nabla} a$, is equivelant to the surface normal at any point on the surface.

This is easy to compute in Python, using a central limit appoximation of the spatial derivatives,

D_ = 1e-4
DX = A([D_,0,0])
DY = A([0,D_,0])
DZ = A([0,0,D_])

def G(sdf,pts):
'''Computes the gradient of the SDF scalar field'''
return A([sdf(pts+DX)-sdf(pts-DX),
sdf(pts+DY)-sdf(pts-DY),
sdf(pts+DZ)-sdf(pts-DZ)]).T/(2*D_)

and isn’t any harder in GLSL.

const float D_ = 1e-4;
const vec3 DX = vec3(D_,0.0,0.0);
const vec3 DY = vec3(0.0,D_,0.0);
const vec3 DZ = vec3(0.0,0.0,D_);
return vec3(sdf(p+DX)-sdf(p-DX),
sdf(p+DY)-sdf(p-DY),
sdf(p+DZ)-sdf(p-DZ))/(2.0*D_);
}

It is typical for the intersection code to pre-compute the gradient at the intersection point, to confirm it is in fact moving nominally torward the surface. Ultimately illumination from any source is proportional to the dot product of the direction to the source and the surface normal.

#### Diffuse reflectivity

Diffuse reflectivity models the reflected light that is reflected uniform in direction from a surface, giving surfaces their color. In principle, all light arriving at a surface is diffusely reflected in part back to the viewer, and must be taken into account. Therefore, handling diffuse reflectivity ammounts to accounting for all light arriving at a surface, if possible.

#### Specular reflectivty

Specular reflections are highly directional in nature, and the outgoing ray is in the same plane as and at the same angle from the normal vector. Accounting for specular reflection is therefore accounting for light arriving from a particular direction, which can be determined by the illumination of the surface in the direction of the reflection. This part is recursive, and requires running the full lighting stack for the reflected rays. Easy enough to do on a CPU, in GLSL this was accomplished with a finite stack and finite loop, each of sufficient size for non-pathological cases. Each step in the process usually has some inefficiency (nothing is 100% refective) so even in a very reflective environment, contributions from repeated reflections get smaller as the number of reflections increases.

#### Transmission

Transmission, particularly when refractive indices are different and refraction is significant, adds some complications. Foremost is that occlusion calculations relying on geometry intersection are no longer valid when surfaces may transmit. The fix to this also cannot be a straight line approximation through transparent objects due to refraction. Occlusion becomes a problem with no closed form solution, requiring iterative or exhausstive search methods to solve.

Of secondary consideration is that the renderer must either gracefully handle light being inside objects, or have a special case to determine an ultimate exit point, if one exists. I opted for the latter, just to get it working, but might revisit in the future. This then works like reflection, just from another direction and another point for the outgoing ray.

#### Going further

Not all reflections are exactly diffuse or exactly specular. What’s worse, reflectivity and transmission are linked and a fucntion of incidence angle for transmissive surfaces. We also know no real surfaces are perfectly smooth, which impacts everything discussed. These details could be improved for more realistic models, and indeed are included in simulations of optics within physics experiments.

### 3. Determine the lighting (color/brightness)

Eventually reflected and transmited rays will all terminate at some point where the lighting must be calculatd. I’ve explored two lighting schemes to go along with the SDF geometry and casting framework. The first is what I’ll call direct lighting where sources of light are defined, and the visibility of any point can be calculated by casting rays within the geometry. This method is very fast and is suitable for realtime demonstrations, but is limited in terms of the optical effects it can handle. The second I’ll call true optics where certain objects in the scene generate light, and the true behavior of light is simulated to light the image. While this can produce results indistinguisable from real life, it requires significantly more computation, and only appoximations (clever tricks) can get this running in real time.

#### Direct lighting

Since the discussion of surface properties indicates that all properties other than diffuse reflectivity are simply accounting for diffuse light from other surfaces, one needs only to account for how surfaces are lit in a diffuse sense to render an image. If a light has some color $\vec{C}_L$ and is at some position $\vec{X}_L$, the surface at position $\vec{x}$ with normal $\hat{n}$ is illuminated by $$\vec{I} = \vec{C}_L\frac{\left(\vec{X}_L-\vec{x}\right)\cdot\hat{n}}{\left|\vec{X}_L-\vec{x}\right|^3} = \vec{C}_L\frac{\hat{n}_L \cdot \hat{n}}{L^2}$$ where $\hat{n}_L$ and $L$ are the direction and distance to the light, respectively. This holds as long as no other surface occludes the light from the perspective of the surface. A similar form for a distant light replacing $\vec{C}_L / L^2$ with the value of direct illumination.

The inverse proportionality to the distance squared is a deep relationship to three dimensional geometry, and describes how the intensity of light decreases with distance. The dot product describes how the illumination of the surface with respect to the direction of the light is maximal when the normal and direction is aligned $\alpha = 0$ and behaves as $\cos \alpha$ for other angles. Finally, the illumination $\vec{I}$ of the color of the surface $\vec{C}$ is observed as a luminance $\vec{L}$ $$\vec{L} = \vec{I}\odot\vec{C} + \vec{E}$$ where $\odot$ denotes element-wise multiplication escribing the mixing of a color of light with a pigment, and $\vec{E}$ is the emissivity property, that will be more important in the next section.

The approximations come in at two points: the occlusion calculation cannot handle complex light paths gracefully, and the description of light sources. Occlusion has partially been discussed, as it relates to finding refracted paths of light being difficult. A more subtle issue is that reflective surfaces can reflect light onto other surfaces, which isn’t accounted for at all, but falls under the umbrella of occlusion. The shortcomings related to light soruces are perhaps the most evident: point sources and directional/distant sources will produce knife edge shadows, which a keen eye will recognize as unrealistic.

Both of these approximations in light source and possible paths makes direct lighting deterministic and very fast. Surfaces where there’s a weighted mix of several effects simply produces the weighted result of those directly calculated effects. In many situations where caustics or illumination through a transparent/reflective surface isn’t present, this produces reasonable results, especially with techniques to smooth shadows. Indeed, this approach of backtracking rays through to diffuse surfaces to be illuminated is most similar to modern real-time rendering, where effects not reproduced by this approach are shoehorend in with approximations.

#### True optics

Fortunately, it’s possible to just get all the optics right with, in some sense, an easier approach, as long as you have copious amounts of processing power available. Understanding this is as simple as realizing this whole lighting exercise is “just” integrating the independent contributions of the entire scene. This integration problem can be solved with a traditional monte-carlo approach, tracing hypothetical photons back to where they came from to determine their intensity. This is similar to the direct lighting backtracking approach, but at a surface exactly on branch (transmit, diffuse, specular) is chosen, removing the recursive factor.

For diffuse reflection, instead of attempting to calculate the contribution of each light to the surface, a random reflection direction is generated and the tracing continues. The only way for the pixel corresponding to a ray to be lit is for this process to eventually land on a surface with emissivity $\vec{E}$. Before, this was just a color a surface had independent of illumination. Now, this is the only source of light.

Given the totally random nature of diffuse reflection, many traces will result in no emissive object being found. To produce an image, many hundreds or thousands of traces must be done to properly integrate the light sources, or some more intelligent integration technique must be used. Either way, while this produces all effects of light one might expect to see in real life, it is typically far too slow to employ without approximations in realtime applications.

## sdfray rendering engine

Without further delay, the sdfray package implements the rendering fraemwork described in the previous sections, using signed distance function primitives to build a constructive solid geometry, and both direct and true lighting models. I designed it to be easy to construct geometries in, and it is in a usable state for generating simple scenes. sdfray is built on fairly standard Python packages, with the exception of ModernGL which I’ve found to be a refreshing and elegant way to run GLSL shaders, and highly recommend.

My ultimate goal in designing this was to get refraction working, and use it to render some caustics. To save you from clicking the link, caustics are light patterns produced by refracting or reflecting off a non-flat surface. This is an advanced feature of rendering, and not something typically taclked in game engines. Notably, the direct lighting style would have no chance of rendering a caustic, but it was crucial (in its speed) for testing and proving out the framework. With that in mind, I’ll step through some of the highlights along the development path.

### Examples from sdfray

Probably the lowest bar is “can you render a sphere” for which the answer is assuredly yes, after some preliminaries.

from sdfray.light import DistantLight,PointLight,AmbientLight
from sdfray.scene import Scene,Camera
from sdfray.geom import Union,Intersection,Subtraction
from sdfray.shapes import Sphere,Box,Cylinder,Plane
from sdfray.surface import UniformSurface,SurfaceProp,CheckerSurface
from sdfray.util import *

import numpy as np

The general idea is that one defines the SDF for the geometry, and, if using the direct lighting model, some flavor of lights to illuminate the scene. The SDF is simple

sdf = Sphere()

where we’ve made heavy use of defaults, getting a unit sphere with a nominally diffuse surface. This python object is callable to evaluate the SDF, and inherits from the SDF class to give it the ability to generate GLSL shader code, among other things.

I’ll generate several lights with different colors, one distant, and a bit of ambient lighting for contrast with the background.

lights = [
PointLight([10,0,0],[2,2.5,-2]),
PointLight([0,10,0],[-2,2.5,0]),
DistantLight([0,0,1.5],[2,2.5,2]),
AmbientLight([0.1,0.1,0.1])
]

From this, a Scene that can be rendered can be created.

Scene(sdf,lights).render()

A slightly more complex demo of the CSG capability can be done.

cut_x = Cylinder(height=3,radius=0.5,rotate=[0,0,np.pi/2])
sdf = Subtraction(Subtraction(Subtraction(box_sphere,cut_x),cut_y),cut_z)

Scene(sdf,lights).render()

Showing off reflection capability is easier with something more complex still

glossy = SurfaceProp(diffuse=0.05,specular=0.85)
demo_sdf = Union(sdf,Plane(surface=CheckerSurface()))
demo_lights = [
PointLight([50,0,0],[2,2.5,-2]),
PointLight([0,50,0],[-2,2.5,0]),
PointLight([0,0,50],[2,2.5,2])
]
Scene(demo_sdf,demo_lights).render()

Adding in several shapes with different properties, including transmission.

mega_demo_lights = [
PointLight([25,0,0],[2,2.5,-2]),
PointLight([0,25,0],[-2,2.5,0]),
PointLight([0,0,25],[2,2.5,2])
]

sdf = Union(Box(translate=[-1.5,-0.2,0],depth=1.4,height=1.4,width=1.4,surface=UniformSurface(SurfaceProp(diffuse=0.9,specular=0.1))),sdf)

mega_demo_sdf = Union(sdf,Plane(anchor=[0,-1,0],surface=CheckerSurface(checker_size=0.25)))
Scene(mega_demo_sdf,lights=mega_demo_lights,cam=Camera(width_px=1920)).render()

This is approximately the point at which the CPU renderer was too slow for rapid work, and I started moving towards GLSL. Generating GLSL from the Python geometry is worth an entire other blog post, but suffice to say this opened up the possibility of adding motion in the form of per-frame parameters. GLSL accomplishes this with uniforms which are values are passed to each thread of the shader rendering a scene. I’ve adopted u_time as a value that increases every frame, and created a scheme for these parameters to be used in any part of the scene description.

This is a simple scene where the camera will orbit the origin.

ctx = Context()
t = ctx['u_time']
ct = np.cos(t)
st = np.sin(t)
c = Camera(camera_orig=10*A([st,0,-ct]),camera_yaw=-t,width_px=700)

Rendering it requires some additional code, which I haven’t baked into sdfray yet, which handles the broiler plate task of encoding frames as an MP4 video.

import io
import imageio
import base64
from IPython.display import HTML

def encode_mp4(scene,times=np.linspace(0,2*np.pi,600),fps=60,framedir=None,**kwargs):
try:
os.mkdir(framedir)
except:
pass
output = io.BytesIO()
scene.clear_cache()
with imageio.get_writer(output, format='mp4', mode='I', fps=fps) as writer:
for i,time in enumerate(times):
v = scene.render(time=time,**kwargs)
if framedir is not None:
v.save(f'{framedir}/frame_{i:05d}.png')
writer.append_data(np.asarray(v))
output.seek(0)

def display_mp4(mp4,fname=None):
if fname is None:
b64 = base64.b64encode(mp4)
src = f'data:video/mp4;base64,{b64.decode()}'
else:
with open(fname,'wb') as fout:
fout.write(mp4)
src = fname
display(HTML(f'<video controls loop src="{src}"/>'))

Then we can render:

display_mp4(encode_mp4(s))

And at this point something can be designed that exceeds the capabilities of the direct lighting engine.

ctx = Context()
t = ctx['u_time']
ct = np.cos(t)
st = np.sin(t)
c = Camera(camera_orig=10*A([st,0,-ct]),camera_yaw=-t,width_px=704)

glossy = UniformSurface(SurfaceProp(diffuse=0.2,specular=0.8))
clear = UniformSurface(SurfaceProp(diffuse=0.05,specular=0.1,transmit=0.85,refractive_index=1.4))

sdf = Union(Box(translate=[-2,0,0],rotate=[0,3*t,2*t],depth=1.5,height=1.5,width=1.5,surface=clear),sdf)

clear_demo_sdf = Union(sdf,Plane(anchor=[0,-1,0],surface=CheckerSurface(checker_size=0.25)))

point_lights = [
PointLight([50,0,0],[2,2.5,-2]),
PointLight([0,50,0],[-2,2.5,0]),
PointLight([0,0,50],[2,2.5,2])
]

s = Scene(clear_demo_sdf,point_lights,cam=c)

display_mp4(encode_mp4(s))

Looking carefully at the area under the rotating shapes, it can be seen that there’s more shadow that one would expect underneath a transparent shape. This is due to how the occlusion calculation is done in direct lighting engine. I’m only at the earliest stages of getting the true optics engine working well, but here is a teaser showing the promised caustics underneath the transparent shapes in the same scene.

display_mp4(encode_mp4(s,true_optics=True))

• The grain is due to the random sampling of light paths in integration, and that I haven’t randomly sampled enough. There are 1000 samples per pixel here.
• The point lights have been converted to emissive spheres, which I grant are a bit silly, but give a good apples-to-apples comparison.
• The light patterns from refracted and reflected light below the transparent shapes meets my original goal.

There’s still a lot more I want to do with this, but it’s certainly at a satisfying place for now!

## Realtime GLSL demos

This is a good time to highlight that the previous visualizations were MP4 videos, but modern browsers can render 3D content in realtime using WebGL. Running a shader directly with WebGL is a bit of a pain, as I understand it, but frontends like glslCanvas make this painless. What’s better: shader code generated by sdfray is almost drop in compatible with glslCanvas. Here is one example showing off the accurate handling of refraction and reflection, realtime, using glslCanvas and WebGL.

And another showing off the kinds of distortions that can be applied to SDFs for interesting effects.

Watch the sdfray repository for updates to the rendering engine, and check back for some deep dives into some of the capabilities listed here.

>> Home


text:
# Zettelkasten Forum

edited September 2020

My reference material has been moving around over the years, because a final storage solution is still under development. I am trying to fix this problem but still don't have a clear understanding of my requirements.

Specifically, i wonder how stable linking is when using Evernote. Personally, i don't use it but i noted that reference material is stored with UIDs. Can someone share his / her experience with using these? Have you had any broken links after moving, copying, deleting material within Evernote?

Additionally i was wondering how @Will is using his links in the form of evernote:///view/.... How do you navigate from your Zettel to the referenced material?

Generally, i need a better understanding of the challenges of storing reference material. This is merely a reminder to my self, i may reply to this post as more specific questions arise.

my first Zettel uid: 202008120915

• @zk_1000 as you know Evernote hides metadata from the user and stores this all in a proprietary DB. The UID's are not esthetic, to put it mildly. I use a Keyboard Maestro macro to place the UID in the right format so it creates a link in The Archive that will launch or bring Evernote to the front and open the appropriate note in Evernote.

I've evolved the macro so that I can capture the title of the note and paste it with the link.
The two notes referred to in the image below are Create an Idea Index and Maria Popova on Writing and they are the titles of the notes and got copied from Evernote in the macro.

Let me explain my current thinking on reference material.
1. I mostly use the /media directory file scheme that is the default in The Archive and I'm hoping that in a future version of The Archive we will have some auto previewing and as this is the standard file/image repository, keeping most reference material here may make the transition easy. My /media directory is 200 meg. My zettelkasten is 2.1 meg. Both are a mere pittance in today's digital environment.
2. I use BibDesk as my reference manager and it can store documents of about any type in reference to a book or paper or webpage or any reference item you'd want.

The mix empirically feels like 60% /media, 30% Evernote, 10% BibDesk. This is an evolving thing. I don't think one tool will meet all my use cases but these three have suited me well and I am relaxed in that I will not loose and references.

BibDesk reference

Will Simpson
“Read Poetry, Listen to Good Music, and Get Exercise”
kestrelcreek.com

• @Will thank you for your reply. I was really curious about your workflow, since you've mentioned before that you have a lot of experience with Evernote.

I see that you have page indications for your references, meaning that you have one reference per citation? I cannot imagine how this can work out, with hundreds of page references from the same book my auto completion would probably be unusable. Also, wouldn't you have to fill in author information for every reference again and again? What i do, instead, is having one reference for a book, then do my note taking and page numbers in a literature note outside of Zotero.

my first Zettel uid: 202008120915

• @zk_1000 said:
I see that you have page indications for your references, meaning that you have one reference per citation? I cannot imagine how this can work out, with hundreds of page references from the same book my auto completion would probably be unusable. Also, wouldn't you have to fill in author information for every reference again and again? What i do, instead, is having one reference for a book, then do my note taking and page numbers in a literature note outside of Zotero.

Good eye, but you misinterpret the reference entry in BibDesk. I keep my citations in one - many relationships much like you. It would hard and way too much work to create an entry in the reference manager for every citation. I can see how this entry might have led you to believe I was keeping citations in my reference manager. This is an "article" reference type. An article in Volume 8. None of the other articles in the volume are being referenced and the article is on pg 28-38. How would you do this in Zotero? Would you reference the entire volume? Or reference the whole journal series?

This is how I used this reference. It turns out I used it only once so far. You can see that the Keyboard Maestro macro I use to put the citation in the note grabs the volume and page numbers of the article automatically according to my custom export template in BibDesk. I have other references that have up to 100 citations and for those, I enter the page numbers on the note I create the note and citation, much like you.

The whole reason for showing the image of BibDesk was because I use it as a storage place for reference materials. In this case, the PDF of the article is stored in BibDesk, not directly on the file system nor in Evernote. Zotero must have the same capabilities?

Will Simpson
“Read Poetry, Listen to Good Music, and Get Exercise”
kestrelcreek.com

• I forgot to mention i am a greenhorn when it comes to reference managers.

None of the other articles in the volume are being referenced and the article is on pg 28-38. How would you do this in Zotero? Would you reference the entire volume? Or reference the whole journal series?

I haven't had this scenario before but i'm sure there is a way to do similar things with Zotero.

Yes, Zotero can also be used to store reference material. I haven't considered this option yet. The cite keys are changing as well from noauthor_nodate to ahrens_how_2017. I am still hesitant in using Zotero, it's most likely not the Software i'm going to stick with.

my first Zettel uid: 202008120915

• @Will said:
This is how I used this reference. It turns out I used it only once so far. You can see that the Keyboard Maestro macro I use to put the citation in the note grabs the volume and page numbers of the article automatically according to my custom export template in BibDesk. I have other references that have up to 100 citations and for those, I enter the page numbers on the note I create the note and citation, much like you.

This is very nice, could you share the Keyboard Maestro macro you use to include your references?

• @tantrig here is the Keyboard Maestro macro. BibDesk Reference Insertion. It was one of my early macro builds and it took quite some time to get right. It works reliably for me and I've found no need to improve it. I remember it as being quite fiddly to get working. It takes some research in figuring out how to create and make available "export templates". There are a few dependencies needed for this to work, I think, really I can't remember why I needed them.

It was a learning experience to build this. Good Luck.

Will Simpson
“Read Poetry, Listen to Good Music, and Get Exercise”
kestrelcreek.com

• Good news is that i was able to fix a huge pile of headache i had with zotero. I am now more confident that this is the tool i want to stick with.

The mix empirically feels like 60% /media, 30% Evernote, 10% BibDesk. This is an evolving thing. I don't think one tool will meet all my use cases but these three have suited me well

I am still struggling to decide what goes where. Unfortunately i don't know anyone with a MacOS so i have no way to test The Archive. @Will Can you explain a bit why you use the default file scheme of TA and why it is a better fit than Evernote or Bibdesk?

my first Zettel uid: 202008120915

• @zk_1000 said:
Good news is that i was able to fix a huge pile of headache i had with zotero. I am now more confident that this is the tool i want to stick with.

Great, I think you'll be happy with Zotero. It is well supported in the academic community. It is supported in all the operating systems that matter, unlike BibDesk which is Mac only.

Can you explain a bit why you use the default file scheme of TA and why it is a better fit than Evernote or Bibdesk?

I use three thought processes when deciding where to store reference material.
1. I tend to favor using The Archives /media scheme on the hopes, fingers crossed, @ctietze will extend that scheme in V.2 of The Archive so zettel will have auto-preview. Using this method will set me up so I'll not have to make formatting changes and when this feature is available I'll already be set. - These files are mostly but not exclusively images.
2. If a reference is already in Evernote I'll keep it there and use my Evernote to The Archive linking. These files are mostly but not exclusively web clippings.
3. The third thought process I sometimes use is embarrassing - call it lazy, call it inattention, call it expediency. Sometimes I put the reference material in whichever bucket is handy. No rhyme or reason. This will probably come back to bit me but for now, it seems a distraction to spend too much time focused on this.

I don't have a use case for a more stringent reference storage scheme but I could picture use cases where this would be an important consideration.

Turns out that I've stored only PDF's in my reference manager, BibDesk, but there are PDF's in Evernote and in /media.

Will Simpson
“Read Poetry, Listen to Good Music, and Get Exercise”
kestrelcreek.com

• If I store the reference material I just change the file name to [date-author-title] and keep it in a separate folder. An alternative is to name the file with the citekey you are using. However, it is always just a folder full of documents.

I am a Zettler

• @Will said:
1. I tend to favor using The Archives /media scheme on the hopes, fingers crossed, @ctietze will extend that scheme in V.2 of The Archive so zettel will have auto-preview. Using this method will set me up so I'll not have to make formatting changes and when this feature is available I'll already be set. - These files are mostly but not exclusively images.

Displaying images in the notes is supposed to hit sooner than version 2

I use BibDesk in much the same way. I have a folder called literature next to media -- media is for attachments to Zettel like images, and literature is for my reference database file + its attachments. For the PDFs I sometimes attach to reference entries, I use the citekey of the entry, too. So when I search for kant1793 I get everything at once, and if the BibTeX format should ever vanish from this earth, I can manually figure out which PDF goes with which reference entry without problem. (That's what you get when you become paranoid about file formats and longevity ...)

Author at Zettelkasten.de • https://christiantietze.de/

• @sfast said:
If I store the reference material I just change the file name to [date-author-title] and keep it in a separate folder. An alternative is to name the file with the citekey you are using. However, it is always just a folder full of documents.

Hi Sascha!
Do you have a solution for automatic conversion of the file name into [date-author-title]? I have been using this exact format for years. But I download dozens of articles weekly, say from Jstor where they have titles like 8978787423, and it is cumbersome to change them manually, one by one. I'd pay a small fortune for a tool that extracts that info from a bulk of pdfs, and then names each pdf accordingly.

Thanks!

PS: I'm a new user of both The Archive and BibDesk, and just figuring out how to integrate both into the workflow.

• @Dragonfly said:
Do you have a solution for automatic conversion of the file name into [date-author-title]? I have been using this exact format for years. But I download dozens of articles weekly, say from Jstor where they have titles like 8978787423, and it is cumbersome to change them manually, one by one. I'd pay a small fortune for a tool that extracts that info from a bulk of pdfs, and then names each pdf accordingly.

Bookends will do it. And you could probably do it with Hazel, though I haven't tried that. I use Hazel for automatically renaming bills and receipts.

• thanks for sharing. For reference, Bookends for iOS is from Sonny Software. Hazel is from noodlesoft.

I always wondered why there are so many here using Apple products - now I know! There's tons of useful software.

my first Zettel uid: 202008120915

• @Dragonfly said:

@sfast said:
If I store the reference material I just change the file name to [date-author-title] and keep it in a separate folder. An alternative is to name the file with the citekey you are using. However, it is always just a folder full of documents.

Hi Sascha!
Do you have a solution for automatic conversion of the file name into [date-author-title]? I have been using this exact format for years. But I download dozens of articles weekly, say from Jstor where they have titles like 8978787423, and it is cumbersome to change them manually, one by one. I'd pay a small fortune for a tool that extracts that info from a bulk of pdfs, and then names each pdf accordingly.

Thanks!

PS: I'm a new user of both The Archive and BibDesk, and just figuring out how to integrate both into the workflow.

The answer to all questions if I have a solution for automatic anything is no. I just get on Christian's nerves until a solutions somehow emerges.

I am a Zettler

• @MartinBB said:

@Dragonfly said:
Do you have a solution for automatic conversion of the file name into [date-author-title]?

Bookends will do it. And you could probably do it with Hazel, though I haven't tried that. I use Hazel for automatically renaming bills and receipts.

Thanks MartinBB! I'll check those out.


text:
# Asymptotic Analysis for Reliable Data Dissemination in Shared loss Multicast Trees Academic Article

•
• Overview
•

### abstract

• The completion time for the dissemination (or alternatively, aggregation) of information from all nodes in a network plays a critical role in the design and analysis of communication systems, especially in real time applications for which delay is critical. In this work, we analyse the completion time of data dissemination in a shared loss (ie, unreliable links) multicast tree, at the limit of large number of nodes. Specifically, analytic expressions for upper and lower bounds on the expected completion time are provided, and, in particular, it is shown that both these bounds scale as $\alpha\log n$. For example, on a full binary tree with $n$ end users, and packet loss probability of $0.1$, we bound the expected completion time for disseminating one packet from below by $1.41\log_2 n+ o\left (\log n\right)$ and from above by $1.78\log_2 n+ o\left (\log n\right)$. Clearly, the completion …

### publication date

• January 1, 2015


text:
Disturbance-Observer-Based Robust H Switching Tracking Control for Near Space Interceptor

Title & Authors
Disturbance-Observer-Based Robust H Switching Tracking Control for Near Space Interceptor
Guo, Chao; Liang, Xiao-Geng;

Abstract
A novel robust $\small{H_{\infty}}$ switching tracking control design method with disturbance observer is proposed for the near space interceptor (NSI) with aerodynamic fins and reaction jets. Initially, the flight envelop of the NSI is divided into small subregions, and a slow-fast loop polytopic linear parameter varying (LPV) model is proposed, to approximate the nonlinear dynamic of the NSI, based on the Jacobian linearization and Tensor-Product (T-P) model transformation approach. A disturbance observer is then constructed, to estimate the modeled disturbance. Subsequently, based on the descriptor system method, a robust switching controller is developed, to ensure that the closed-loop descriptor system is stable with a desired $\small{H_{\infty}}$ disturbance attenuation level. Furthermore, the outcome of the proposed switching tracking control problem is formulated as a set of linear matrix inequalities (LMIs). Finally, simulation results demonstrate the effectiveness of the proposed design method.
Keywords
Linear parameter varying (LPV);Disturbance observer;Switching tracking control;Near space interceptor (NSI);
Language
English
Cited by
References
1.
Wang, W., "Near-space vehicle-borne SAR with reflector antenna for high-resolution and wide-swath remote sensing", IEEE Transactions on Geoscience and Remote Sensing, Vol. 50, No. 2, 2012, pp. 338-348.

2.
Davis, M., and White, J., "X-43A flight-test-determined aerodynamic force and moment characteristics at Mach 7.0", Journal of Spacecraft and Rockets, Vol. 45, No. 3, 2008, pp. 472-484.

3.
Xing, L., Zhang, K., and Chen, W., et al., "Optimal control and output feedback considerations for missile with blended aero-fin and lateral impulsive thrust", Chinese Journal of Aeronautics, Vol. 23, No. 4, 2010, pp. 401-408.

4.
Zhou, D., and Shao, C., "Dynamics and autopilot design for endoatmospheric interceptors with dual control systems", Aerospace Science and Technology, Vol. 13, No. 6, 2009, pp. 291-300.

5.
Thukral, A., and Innocenti, M., "A sliding mode missile pitch autopilot synthesis for high angle of attack maneuvering", IEEE Transactions on Control Systems Technology, Vol. 6, No. 3, 1998, pp. 359-371.

6.
Zhao, M., Wei, M., and He, Q., "Research on method of lateral jet and aerodynamic fins compound control based on finite time stability and backstepping approach", Journal of Astronautics, Vol. 31, No. 9, 2010, pp. 2157-2164.

7.
Li, Z., Wei, M., and Zhou, D., et al, Technology of lateral thrust and aerodynamics blended control for anti-air missile, China Astronautic Publishing House, Beijing, 2012.

8.
Petres, Z., Polytopic decomposition of linear parameter varying models by tensor-product model transformation, Budapest University of Technology and Economics, Budapest, 2006.

9.
Wu, F., and Cai, X., "Switching fault-tolerant control of a flexible air-breathing hypersonic vehicle", Proceedings of the Institution of Mechanical Engineers, Part I: Journal of Systems and Control Engineering, Vol. 227, No. 1, 2013, pp. 24-38.

10.
Zhou, K., Doyle, J., and Glover, K., Robust and Optimal Control, Prentice Hall, Englewood Cliffs, New Jersey, 1995.

11.
Yu, S., Yu, X., and Shirinzadeh, B., et al., "Continuous finite-time control for robotic manipulators with terminal sliding mode", Automatica, Vol. 41, No. 11, 2005, pp. 1957-1964.

12.
Chen, W., "Disturbance observer based control for nonlinear systems", IEEE/ASME Transactions on Mechatronics, Vol. 9, No. 4, 2004, pp. 706-710.

13.
Wei, X., and Guo, L., "Composite disturbanceobserver- based control and $H{\infty}$ control for complex continuous models", International Journal of Robust and Nonlinear Control, Vol. 20, No. 1, 2010, pp. 106-118.

14.
Yang, J., Li, S., and Sun, C., et al., "Nonlineardisturbance- observer-based robust flight control for airbreathing hypersonic vehicles", IEEE Transactions on Aerospace and Electronic Systems, Vol. 49, No. 2, 2013, pp. 1263-1275.

15.
Tanaka, K., Ohtake, H., and Wang, H., "A descriptor system approach to fuzzy control system design via fuzzy Lyapunov functions", IEEE Transactions on Fuzzy Systems, Vol. 15, No. 3, 2007, pp. 333-341.


text:
# What is the 40 percent of 8 squares?

Mar 2, 2018

$25.6$

#### Explanation:

$40$ percent of ${8}^{2}$

Let's write this in "math language"

40% xx 8^2

NOTE 40% is the same as $0.4$

$0.4 \times 64$

$25.6$