Generalized Gosper Space Filling Curves and Infinite Series of Them

Jin Akiyama, Hiroshi Fukuda, Hiro Ito, and Gisaku Nakamura
School of Administration and Informatics, University of Shizuoka,
52-1 Yada, Shizuoka 422-8526, Japan

Abstract

The Gosper curve is a space filling curve discovered by William Gosper, an American computer scientist, in 1973, and was introduced by Martin Gardner in 1976 [1,2]. It is constructed by recursively replacing a dotted arrow, called the initiator, by seven arrows, called generator, as shown in Fig. 1(a), Fig. 1(b) and Fig. 1(c) illustrate the curves obtained by replacing the initiator by generator once and twice respectively.


The Gosper curve is said to be monster curve since it is a path from the root to the tip of the initiator without any branches visiting all interior lattice points on a regular triangular lattice. In 2001[3], we found a lot of such monster curves, namely, generalized Gosper curves, by computer search. Their shapes are similar to the original Gosper curve as shown in Fig. 2. In this work, we report on the following three new results.

Figure2:Generalized Gosper curve with N = 13,43,91.


Size of Curves
We investigate the necessary conditions for the size of the curves N, the number of arrows included in the generator. We can show N has to satisfy

N=6n+1, n = 1,2,3,....

and
N=x2+y2+xy,x=0,1,2,...., y=0,1,2,...., (x,y) (0,0).

Therefore possible sizes for generalized Gosper curves are

N=7,13,19,25,31,37,43,49,61,67,73,79,91,97,....

Number of CurvesWe did computer search for the generalized Gosper curves for N 61. Then we could determine the number of generalized Gosper curves CN for given N. We obtained CN = 1,1,1,0,7,8 and 24 for N = 7,13,19,25,31,37 and 43, respectively. For N > 43, calculations are not finished and we found C49134+75 and C61485.

Infinite Series of Curves

We discussed the natural extension of the Gosper curve in [3]. It is a simple procedure to generate infinitely many curves with N = 3k2+3k+1, k=1,2,3,... from Gosper curves as shown in Fig. 3, where we can find simple relation between successive generators in k. We apply this simple procedure for other curves, and so far as our investigation is concerned, more than three quarters of Gosper curves can generate infinitely many curves. For example, the curve with N=13 shown in Fig.2 generates infinite series with N = 9k2+3k+1,. Two curves with N=43 and 91 in Fig.2 are those for k=2 and 3 in this series.

Figure3:Infinite Series of Gosper curve with N = 3k2+3k+1




References

1.M. Gardner, In which 'monster' curves force redefinition of the word 'curve', Scientific American 235 (1976) 124--133.
2.B. B. Mandelbrot, The Fractal Geometry, W. H. Freeman and Company, New York, 1977.
3.H. Fukuda, M. Shimizu and G. Nakamura, New Gosper Space Filling Curves, Proceedings of the International Conference on Computer Graphics and Imaging (CGIM2001),(2001) 34--38 .