A way for Spiderman to catch the Green Goblin

Some years ago, we worked on a problem in digital halftoning for which we could prove a result [1] which states that there is a variant of the vector error diffusion algorithm such that the sum of the errors is bounded. This implies that the average error decreases to 0 as the number of errors to be averaged increases. This is paraphrased as saying that averaging a large area of the halftoned image is similar to the average of the original image over the same area, which is what we expect a halftoning algorithm to behave. In the course of this research, I came up with the following scenario to which this result also provide a solution to, and I have used it to describe this problem to a lay audience. In celebration of Spiderman's well received introduction to the Marvel Cinematic Universe, I thought I'll describe it here:

Consider a city whose shape is a convex polygon, with a building at each corner of this polygon. The main villain Green Goblin (GC) is loose in the city and it is up to Spiderman (S), our friendly neighborhood superhero, to catch him. At the start, GC and S are located at different places in the city. Because of fatique or lack of fuel, at each time epoch, both GC and S are moving less and less. However, whereas GC can move arbitrarily within the city, S (being a webslinger) can only move toward a building at the corner of the city, along the line connecting S and this building.

More precisely, time is divided into epochs numbered 1, 2, 3, ...
At the k-th epoch:

1. GC picks a destination within the city to move to and moves 1/k of the distance in the direction towards the destination.
2. S can moves 1/k of the distance to a building located on the corners of the city, in the direction of that building.

The question is: can S ever catch up to GC?  The result in [1] shows that the answer is yes and gives an explicit algorithm of which building S should swing from at each epoch in order for S to catch up to GC.

References
[1] R. Adler, B. Kitchens, M. Martens, A. Nogueira, C. Tresser, C. W. Wu, "Error bounds for error diffusion and related digital halftoning algorithms," Proceedings of IEEE International Symposium on Circuits and Systems, 2001, pp. II-513-516.

Lava, donuts and printing

We have just returned from vacation touring the British isles. In particular, we visited the Giant's causeway in Belfast, Northern Ireland. The area is covered by more than 40,000 basalt columns with many of them having a shape close to a hexagonal column (similar to the shape of a pencil). They were formed when lava were cooling and shrinking. Why the hexagonal shapes? This might be due to the fact that a hexagonal lattice arrangement of circles on a plane is the densest arrangement of circles of the same size [1]. The hexagonal lattice arrangement is also the covering of circular disk with the least overlap. Many arrangements of objects in nature such as honeycombs have this hexagonal arrangement. The Voronoi regions of this arrangment are hexagons. Since this arrangement is periodic in two (non perpenticular) axes, one can view this as a periodic packing on the torus, provided the density matches the dimension of the torus. When the density does not match, we don't have a hexagonal packing on the torus, and it is not clear what the densest packing is. This has applications in digital halftoning [2]. The only difference in the halftoning application is that the circle centers are points on a discrete grid on the torus.  We studied 2 algorithms to generate such packing on the torus. The first algorithm is the Direct Binary Search (DBS) algorithm [3] and generate patterns like this:

The second algorithm is based on the Riesz energy minimization theory of Hardin and Saff [4] and we were able to obtain patterns that are more uniform than DBS:

In both cases, they look like the patterns found on Giant's causeway:

In 3 dimensions, the densest packing is the face-centered cubic (FCC) lattice packing (also known as the "canonball" packing).  It was conjectured to be the densest packing by Kepler in 1611, and it was only proved relatively recently by Hales with a proof first announced in 1998 and the correctness of the lengthy proof checked by computer in 2014.

References:
[1] J. Conway and N. J. A. Sloane, "Sphere Packings, Lattices and Groups", Springer, 3rd Edition, 1998.
[2] C. W. Wu, B. Trager, K. Chandu and M. Stanich, "A Riesz energy based approach to generating dispersed dot patterns for halftoning applications," Proceedings of SPIE-IS&T Electronic Imaging, SPIE, vol. 9015, pp. 90150Q, 2014,
[3]  J. P. Allebach, “DBS: retrospective and future directions,” in Proceedings of SPIE, 4300, pp. 358–376, 2001.
[4] D. P. Hardin and E. B. Saff, “Discretizing manifolds via minimum energy points,” Notices of the AMS 51(10), pp. 1186–1194, 2004.

Musical tastes across the generations

One day my son and I were eating at a restaurant and we heard an instrumental piece playing over the speakers.  He said to me: "doesn't this sound familiar?".  I listened to it for a while and indeed it sounded familiar.  It brought back memories from my childhood, as the music is from a song from Hong Kong that I remember when I was much younger. But as my son grew up in the USA, how come it is familiar to him as well? Some quick internet searching reveals that the song is a 1963 instrumental piece called "Washington Square" by the Village Stompers, a band from New York City. It turns out the music was used in 1978 by Sam Hui (許冠傑), one of my favorite Hong Kong singers from my childhood, in a song called 學生哥, roughly translated as "student". It is a catchy song encouraging students to study and become productive members of society. One of the reason Sam Hui's songs are popular is because they use Cantonese slang a lot, as contrasted to more formal Cantonese used by others.  Sometimes the slang words are purely verbal, and there are no written Chinese logograms to describe these words, so he would put English words to phonetically describe these words and many of his song lyrics are full of such words.

Anyway, the reason my son heard of this song that was composed before I was born is because it has been covered in a more modern version called "Faidherbe square" by ProleteR and was used in a Youtube video my son was watching. Of course he prefers the modern version while I prefer the Hong Kong version, but we both liked the original 1963 composition. It is remarkable this music has delighted multiple generations and I am glad we both discovered this music together.

My teenage son wants to go grocery shopping with us

The other day I was going to the grocery store to do some shopping and my son said to me: "I want to go with you to the grocery store."  This has never happened before. He is also spending more time outside. I believe it is all due to this life changing program that my son has downloaded on his phone. It is a proven system (proven within the last week or so) that has gotten many people exercising more and spending more time outside. The basic premise is simple; the goal is to catch small monsters (so called pocket monsters) while wandering around the neighborhood. All I can say is Bravo to the creators of this app!