Wednesday, July 27, 2016

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.