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:
- GC picks a destination within the city to move to and moves 1/k of the distance in the direction towards the destination.
- S can moves 1/k of the distance to a building located on the corners of the city, in the direction of that building.
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.
No comments:
Post a Comment