Category Archives: Visualization

MISG day 5

I didn’t explain the problem well enough in my last post: AGL, the energy supply company, are trying (among other things) to create several “reference profiles” of energy use, to which customers can be compared.  This will give them a better idea about supply and demand, and allow them to more accurately forecast energy requirements.

This was a problem more statistical than mathematical, and people were throwing all sorts of clustering analysis techniques (about which I know nothing) at it.  However, an averaging plot showed two parallel “clumps” of data, which a single curve of best fit couldn’t describe.  Since I know nothing about statistics, but quite a lot about imaging, I had the idea of treating each customer plot as an image:

Notice the two clumps at the bottom left – this is an example of a plot to which a curve of best fit could not be usefully applied.

The image has been subdivided into unequal quadrants, of which the upper left and right parts are the energy usage during hot and cold temperatures.  The vertical dividing line is at 20C = 68F.  The horizontal line is one-quarter from the bottom.  This seemed (without any analysis) to be a good place for cutting off “standard” energy usage (below the line) to “high” usage (above the line.  The customers can then be classified by choosing thresholds for “high hot” and “high cold” usage, and clustering them depending on whether they have used more or less than the threshold value.

The nice thing about his approach is that it’s both very easy and very transparent, and also can be adjusted; for example using finer grids on the image, by subdividing the original data into times of day, or into weekdays/weekends (or both), or by using a better approach than “by eye” to determine the cutoff point between standard and high usage.

The workshop ended before I could explore this idea any further… so I might play around with this on my own some more.

MISG day 3

This week I’m at the Mathematics and Statistics Industry Study Group, a yearly event where companies from Australia and New Zealand provide problems for the assembled mathematicians and statisticians to solve.  I’m in a crowd of people working on a problem provided by the energy company AGL.  They have given us electricity smart meter data for 95 customers (there is a larger data set with 900 customers) of electricity readings taken every 30 minutes over a 199 day period.   That’s 9552 observations for each customer!  You can read the problem here.

So far everybody has (in the words of one participant) “thrown every imaginable package at the data and drawn lots of pretty pictures”.  Other folk are using Excel, Minitab, R and other statistics packages; I’m using Octave.  Today we have decided to break down the data into times of day: night (0000 – 0600), mornings (0600 – 0900), daytime (0900-1700) and evening (1700 – 2400), and to look at electricity usage versus temperature over those times, and over the course of the 199 days, which go from winter to summer.  We can also break down the data into weekdays, and weekends.

Here is an example of one data plot: a customers usage by temperature (which is the horizontal axis and given in celsius, so the upper value, 40, is very hot: 104F).

This customer’s usage, as you can see, is skewed up to the right (where the temperature is hotter), which would seem to indicate the use of an air-conditioner.  Other such plots are skewed to the left (colder temperatures) which would appear to indicate the use of heating in cold weather, but no a/c in hot.  Other plots have humps at both ends.  A few people have been trying to fit quadratic functions to these plots, without a huge amount of success, as the correlation is so low.

If you simple plot the data of a single customer over the entire data period you can see some interesting stuff.  Here for example, is one data set:

Notice the “break” towards the right (this corresponds to early summer).  We can infer that this customer went away at that time, and the residual power usage would have been for refrigerator, maybe security lights etc.

I am not myself any closer to solving the problems proposed by AGL, but I’m getting a better handle on the data.  I still intend to do some data smoothing, probably with a Gaussian filter, and see if it’s possible to classify customers based on the outputs.   Or I might head off to the staffroom in search of tea.

I’m very fond of geometric results which are a bit surprising, but turn out to be easy to prove. Here are two such.

Thébault’s result

The French problemist Victor Thébault published three problems in the late 1930′s. The second problem may be stated thus: on two adjacent sides of a square, construct two equilateral triangles, either both outwards or both inwards. The points at their outer vertices and the square’s opposite vertex form the vertices of another equilateral triangle.

Here’s a picture of the case with outward triangles:

The easiest proof requires a tiny amount of angle chasing. Consider the bottom triangle as pictured here:

The angle at H, being the sum of the internal angles of a square and equilateral triangle is 150°, and since this triangle is isosceles, the outer two angles must be equal and 15°. By symmetry then, the outer two angles at G must be 15° which means that the inner angle is 60°. Since the two edges which form this angle are equal, the triangle is equilateral, as required.

Here’s a sledgehammer proof using vectors. Assume without loss of generality that the square has side length 2, and let ${\bf u}$ be the vector GK, ${\bf v}$ be the vector GL. By construction, we must have

${\bf u} = \langle 2+\sqrt{3},1\rangle$ and ${\bf v} = \langle 1,2+\sqrt{3}\rangle$

Then

$\begin{array}{rcl}\cos\theta &=&\displaystyle{\frac{{\bf u}\cdot{\bf v}}{\|{\bf u}\|\|{\bf v}\|}}\\ &=&\displaystyle{\frac{4+2\sqrt{3}}{1+(2+\sqrt{3})^2}}\\ &=& \displaystyle{\frac{4+2\sqrt{3}}{8+4\sqrt{3}}}\\ &=& \displaystyle{\frac{1}{2}}.\end{array}$

This means $\theta=\pi/3$ as required.

Here is a picture of the case with internal triangles. The proof is very similar to the above case.

Suppose two squares ABCD (vertices given clockwise) and EFGH (likewise) share a common vertex: A and E, say. Then the midpoints of the squares, and the midpoints of the lines BH and DF are the vertices of another square:

First note that this in fact follows from the very general fundamental theorem of directly similar figures: suppose $P=P_0P_1\ldots P_k$ is a polygon (with $P_i$ being its vertices, and suppose $Q=Q_0Q_1\ldots Q_k$ is another polygon obtained from $P$ by translations, rotations, or scalings. The polygons are then said to be directly similar. For any $r$ with $0\le r\le 1$ define the polygon $R$ to have vertices $R_i=rP_i+(1-r)Q_i$. Then $R$ is directly similar to $P$ and $Q$.

The Finsler-Hadwiger theorem follows from this by labelling the vertices $A,B,C,D,E,F,G,H$ as $P_0,P_1,P_1,P_3,Q_2,Q_3,Q_0,Q_2$, and with $r=1/2$. But here’s a direct proof. First observe that vertices $(x_0,y_0)$, $(x_1,y_1)$, $(x_2,y_2)$, $(x_3,y_3)$ are the vertices of a square (given in order around its edges) if and only if

$x_1-x_0=y_1-y_2=x_2-x_3=y_0-y_3$

and

$y_1-y_0=x_2-x_1=y_2-y_3=x_0-x_3$.

Suppose without loss of generality the vertices of the left hand square are $(0,0)$, $(-2,0)$, $(-2,-2)$ and $(0,-2)$, and the vertices of the right hand square be $(0,0)$, $(2a,2b)$, $(2b+2a,2b-2a)$ and $(2b,-2a)$:

The midpoints, in clockwise order, are $(-1,-1)$, $(a-1,b)$, $(b+a,b-a)$ and $(b,-a-1)$. Then the above equalities hold with the top line all being equal to $a$ and the bottom equality all being equal to $b+1$.

Note on figures

The figures were all created using GeoGebra, exported as PNG files, converted to JPG and cropped for uploading into WordPress.

LaTeX multido

The LaTeX multido files provide a way for providing general loop macros in LaTeX. They can be used within pstricks, for creating complex diagrams with repetition. Here’s a little example which draws a number line from -10 to 10:

\documentclass[fleqn]{article}

\usepackage{pstricks,multido}

\begin{document}

\psset{unit=5mm}
\begin{pspicture}(-11,-1)(11,1)
\psline{<->}(-11,0)(11,0)
\multips(-10,0)(1,0){21}{\psline(0,0.3)(0,-0.3)}
\multido{\n=-10+1}{21}{\rput(\n,-1){\small{\n}}}
\end{pspicture}

\end{document}


In general, multido uses a counter (defined with a backslash), with starting and incremental values separated by a plus sign. So that

\multido{\n=-10+1}{21}{...stuff...}


starts the counter \n at -10, and increments it by 1 for 21 times.

I vaguely recall some years ago having seen a nonogram for solving quadratic equations, and I thought it may be a fun thing to do with my students. I couldn’t find what I was looking for, but I did come across a lovely result which seems to have been first noted by a French artillery captain named M. E. Lill (see http://www.pballew.net/Lill_cir.doc for a more complete history). It can be stated as follows:

Let the quadratic $x^2+bx+c=0$ have real roots. Then the circle whose diameter has endpoints $(0,1)$ and $(-b,c)$ cuts the $x$-axis at the root values.

We note in passing that the quadratic given is completely general, for any quadratic can be reduced to that form by dividing through by the leading coefficient. Here are “Lill circles” for the quadratic equations $x^2-3x+2=0$:

and $x^2-2x-3=0$:

I like this result. It seems (at first glance) to be slightly mysterious; it is a wonderful mixture of algebra and geometry, and it’s not quite obvious. In fact, the proof is very simple, and is an elementary application of Euclid’s result that the angle in a semi-circle is a right angle.

Consider the first diagram above, without the circle, but with two extra lines:

Since the angle $AOB$ is a right angle, the bottom two triangles are similar, and so

$\displaystyle{\frac{x}{1}=\frac{c}{b-x}}$.

Multiplying this fraction out produces $x(b-x)=c$ which can be rearranged to produce $x^2-bx+c=0$. Since in this diagram the upper right point is $(-(-b),c)=(b,c)$ this finishes the proof.

Visual Cryptography

In 1979, Adi Shamir (the “S” in RSA) and George Blakely independently produced the concept of “secret sharing”. Suppose group of $n$ people wish to share a secret. The secret is divided into $n$ shares, and each person gets one share. The secret is only recoverable if at least $k$ people share their secrets. Such a scheme, requiring $k$ of $n$ shares is denoted a $(n,k)$ scheme. This clearly has applications to such things as security of trade secrets, or the sharing of military power (a missile can only be launched if two people enter their keys simultaneously). And Shamir and Blakely developed protocols for implementing secret sharing; Shamir with polynomials, and Blakely with intersection of hyperplanes. An elegant introduction to secret sharing can be found here.

The trouble with both Blakely’s and Shamir’s schemes is that they require a fair amount of computational overhead. In 1994, Moni Naor and Shamir developed the concept of “visual cryptography”, where shares are printed on overhead transparencies, which are then overlaid to reveal the secret.

Here’s a little $(2,2)$ example: first the shares:

Share 1

Share 2

And now, what happens when these two shares are overlaid:

Both shares together

Since each share is, in effect, completely random, neither share provides any useful information. The scheme is thus completely secure. It may be considered as a sort of visual one-time pad.

There are a few websites which provide visual cryptography applets: one here, and another here. You can also read the original Naor/Shamir paper.

The algorithm for creating a $(2.2)$ scheme is very simple. Start with a binary image $B$ – this is the secret to be shared. Each share $S_1$ and $S_2$ will be a binary image with dimensions twice those of $B$. For each pixel $p$ of $B$, create a $2\times 2$ random binary matrix $R$. If $p$ is white, place $R$ in both $S_1$ and $S_2$. If $p$ is black, place $R$ in $S_1$, and its complement $1-R$ in $S_2$.

This algorithm can be extended to arbitrary $(n,k)$ schemes, but as $n$ and $k$ get large, the combined shares become harder to read. A good introduction to visual cryptography has been produced by Douglas Stinson. For general $(n,k)$, the idea is to produce $n$-row “basis matrices” $T_1$ and $T_2$. A random permutation of the columns is applied to both matrices. If the pixel $p$ is white, the rows of the permuted $T_1$ are places into the shares; If the pixel $p$ is black, the rows of the permuted $T_2$ are used. For example, here are basis matrices for a $(3,2)$ scheme:

$T_1=\left(\begin{array}{ccc}1&0&0\\ 1&0&0\\ 1&0&0\end{array}\right)$
$T_2=\left(\begin{array}{ccc}1&0&0\\ 0&1&0\\ 0&0&1\end{array}\right)$

Note that any two (or three) rows of $T_1$ produce only one black pixel and two white pixels, where two row of $T_2$ produce two black pixels and one white pixel. The combination will thus be visually distinguishable. It is also easy to construct a $(4,2)$ scheme. Consider the matrices

$A_1=\left(\begin{array}{cc}1&0\\ 0&0\end{array}\right)$,
$A_2=\left(\begin{array}{cc}0&1\\ 0&0\end{array}\right)$,
$A_3=\left(\begin{array}{cc}0&0\\ 1&0\end{array}\right)$,
$A_4=\left(\begin{array}{cc}0&0\\ 0&1\end{array}\right)$

For a white pixel, place a randomly chosen $A_i$ in all shares. For a black pixel, let $\pi$ be a random permutation of the integers 1, 2, 3 and 4. Place $A_{\pi(i)}$ in share $i$.

Naturally there have been many efforts to extend and generalize this basic idea to grayscale and color images, and to “embed” shares in natural images. Many of these generalizations are, to my eyes, unattractive and unconvincing. But one way to share a grayscale image is to quantize it to binary using a halftoning technique – error diffusion works well – and apply the sharing scheme to the resulting binary image. For a color image, let $m_1$, $m_2$ and $m_3$ be its red, green and blue components. Let $R_{i,j}$ be the $i$-th share of $m_j$. Then a color share $S_i$ is created by using $R_{i,1}$, $R_{i,2}$ and $R_{i,3}$, as its red, green and blue components.

A really beautiful animation

Every now and again I come across a mathematical image so powerful that it quite stops me in my tracks. So it was with this magnificent animation:

which shows a “tesseract” (a four dimensional hypercube), being rotated. I wrote to the creator of this astonishing image, Jason Hise, asking how he created it. He was kind enough to write back, and this is how it was done:

1. First, all the vertices of the tesseract were placed at the coordinates $(\pm 1,\pm 1,\pm 1,\pm 1)$.
2. Next, the vertices were rotated according to the rotation matrix

3. After each rotation, the vertices were translated by $(0,0,0,3)$ to make the $w$ value positive.
4. The vertices were projected into $\Bbb{R}^3$ using

$\begin{pmatrix}x\\ y\\ z\\ w\end{pmatrix}\rightarrow\begin{pmatrix}x/w\\ y/w\\ z/w\end{pmatrix}$.

For display, the vertices, edges, and “squares” were rendered using Maya and its scripting language MEL. (I know nothing about these.)

For me, this animation is a superb use of high powered computing for mathematical visualization.

Another one of Jason’s beautiful animations, this one with two simultaneous rotations, is

And here is another rotating tesseract, rendered differently:

There is a nice discussion and explanation about tesseract rotation, with very elegant diagrams, at http://traipse.com/hypercube/index.html.

3D visualization

Most mathematical software will allow you to create elegant graphs and objects in 3D; often you can then move your graph around with the mouse, finding the position at which it looks best. For complicated shapes like minimal surfaces, finding the parameters and position which produce the best view can be more time-consuming than creating the shape itself.

Of course, what you are seeing is a projection of a 3D scene onto the flat plane of your monitor, with all the lighting, shading, perspective and hidden line removal giving the strong impression of a 3D shape.

But how much more powerful the viewing experience would be if the software allowed some sort of stereo viewing! This wouldn’t be at all difficult; for stereo viewing all you need to do is to create two views of an object, from slightly different positions, and then display them simultaneously. And there are different ways of doing this:

1. “Free viewing”, which means placing the views side by side, for either cross-eyed viewing, or parallel viewing. For cross-eyed viewing, your right eye focuses on the left image, and your left eye on the right image. A 3D image will merge from the separate views. For parallel viewing, your right and left eyes focus on the right and left images – this can be done, with practise, by looking “through” the images – until the images again merge into a single 3D image. There’s a nice introduction at

http://www.angelfire.com/ca/erker/freeview.html

2. Create a red-cyan anaglyph image, in essence two views coloured differently and superimposed, so that when viewed with red-cyan glasses a 3D effect is observed. There are examples at the Wikipedia page

http://en.wikipedia.org/wiki/Anaglyph_image

3. Magic eye (autostereogram); otherwise known as a “Single Image Random Dot Stereogram” (SIRDS). Some people can’t see these at all; others have no difficulty. One problem with SIRDS images is that it is almost impossible to produce a coloured image.

Here are some websites of mathematical stereo interest:

1. Stereo 3D Graphics written with Maple:
http://www.math.tamu.edu/~yasskin/maplets/stereo/
Some very nice anaglyph stereo video images. Grab your anaglyph glasses and enjoy!
2. 3D-XplorMath-J:
http://3d-xplormath.org/j/index.html
This is a brilliant piece of software, which shows lots of different objects, in any 3D method of your choice. It is more of a mathematical museum, in that it is limited in its capacity to create totally new objects, but what it does do, it does superbly.

Just to whet your appetite, here is a cross-eyed image of a helix (click on the image to show it in full):

3. If you can see SIRDS images, this one is a beauty, an animation of two interlocked tori (again click on the image to show it in full):