The Botanical Beauty of Random Binary Trees

Devroye, Luc and Kruszewski, Paul (1996) The Botanical Beauty of Random Binary Trees. In: Symposium on Graph Drawing, GD 1995, September 20-22, 1995, Passau, Germany , pp. 166-177 (Official URL: http://dx.doi.org/10.1007/BFb0021801).

Full text not available from this repository.

Abstract

We present a simple mechanism for quickly rendering computer images of botanical trees based on random binary trees commonly found in computer science. That is, we visualize abstract binary trees as botanical ones. We generate random binary trees by splitting based upon the beta distribution, and obtain the standard binary search trees as a special case. We draw them in PostScript to resemble actual botanical trees found in nature. Through flexible parameterization and extensive randomization, we can produce a rich collection of images.

Item Type:Conference Paper
Additional Information:10.1007/BFb0021801
Classifications:J Applications > J.999 Others
M Methods > M.900 Tree
ID Code:47

Repository Staff Only: item control page

References

ADOBE SYSTEMS INC. (1985). PostScript Language Reference Manual. Reading, MA: Addison-Wesley.

ALONSO, L. AND R. SCHOTT (1995). Random Generation of Trees. Dordrecht, The Netherlands: Kluwer Academic Publishers.

ANON, M. AND T. KUNII (1984). Botanical tree image generation. IEEE Computer Graphics Applications 4, 10-34.

BLOOMENTHAL, J. (1985). Modeling the Mighty Maple. In Proceedings of SIGGRAPH'85, Computer Graphics, Volume 19, pp. 305-311.

CHENG, R. C. H. (1978). Generating beta variates with nonintegral shape parameters. Communications of the ACM 21, 317-322.

CHIBA, N., S. OHKAWA, K. MURAOKA, AND M. MIURA (1994). Visual simulation of botanical trees based on virtual heliotropism and dormancy break. Journal of Visualization and Computer Animation 5(1),3-15.

DEVROYE, L. (1986). Non-Uniform Random Variate Generation. New York: Springer-Verlag.

DEVROYE, L. (1994). Lectures Notes for Computer Science 690A-Probabilistic Analysis of Algorithms and Data Structures. Montreal: School of Computer Science, McGill University.

DEVROYE, L. (1995). Universal limit laws for depths in random trees. (Submitted).

DEVROYE, L. AND P. KRUSZEWSKI (1994). A note on the HORTON-STRAHLER number for random trees. Information Processing Letters 52, 155-159.

DEVROYE, L. AND P. KRUSZEWSKI (1995). On the HORTON-STRAHLER number for random trees. (Submitted).

KRUSZEWSKI, P. (1994). Using the HORTON-STRAHLER number to draw trees. Technical Report SOCS-94.1, School of Computer Science, McGill University.

PITTEL, B. (1985). Asymptotical growth of a class of random trees. Annals of Probability 13, 414-427.

PRUSINKIEWICZ, P. AND A. LINDENMAYER (1990). The Algorithmic Beauty of Plants. New York: Springer-Verlag.

RICHTER, J. P. (1970). The literary works of Leonardo Da Vinci (3 ed.). New York: Phaidon Publishers Inc.

STEPHEN, G. A. (1994). String Searching Algorithms. Lecture Notes Series on Computing. New York: Springer-Verlag.

SUGDEN, A. (1984). Longman Illustrated Dictionary of Botany. Essex, UK: Longman Group Limited.

VIENNOT, X. G. (1990). Trees everywhere. In A. Arnold (Ed.), Proceedings of the 15th Colloquium on Trees in Algebra and Programming, Copenhagen, Denmark, May 15-18, 1990, Lecture Notes in Computer Science, Volume 431, Berlin, pp. 18-41. Springer-Verlag.

VIENNOT, X. G., G. EYROLLES, N. JANEY, AND D. ARQUÈS (1989). Combinatorial analysis of ramified patterns and computer imagery of trees. In Proceedings of SIGGRAPH'89, Computer Graphics, Volume 23, pp.31-40.