A new discrete 3D line and 3D polygon, called Supercover 3D line and Supercover 3D polygon, are introduced. Analytical definitions are provided. The Supercover 3D polygon is a tunnel free plane segment defined by vertices and edges. An edge is a Supercover 3D line segment. Two different polygons can share a common edge and if they do, the union of both polygons is tunnel free. This definition of discrete polygons has the “most” properties in common with the continuous polygons. It is particularly interesting for modeling of discrete scenes, especially using tunnel‐free discrete polyhedra. Algorithms for computing Supercover 3D Lines and Polygons are given and illustrated.

Some very impressive results have been obtained in the past few years in plants and trees image synthesis. Some algorithms are largely based on the irregularity and fuzziness of the objects, and use fractals, graftals or particle systems. Others focus on the branching pattern of the trees with emphasis on morphology. Our concern here is the faithfulness of the models to the botanical nature of trees and plants. We present a model which integrates botanical knowledge of the architecture of the trees: how they grow, how they occupy space, where and how leaves, flowers or fruits are located, etc. The very first interest of the model we propose is its great richness: the same procedural methods can produce "plants" as different as weeping willows, fir trees, cedar trees, frangipani trees, poplars, pine trees, wild cherry trees, herbs, etc. Another very important benefit one can derive from the model is the integration of time which enables viewing the aging of a tree (possibility to get different pictures of the same tree at different ages, accurate simulation of the death of leaves and branches for example). The ease to integrate physical parameters such as wind, the incidence of factors such as insects attacks, use of fertilizers, plantation density, and so on makes it a useful tool for agronomy or botany.

This paper presents the average case performance analysis of dynamic data structures subjected to arbitrary sequences of insert, delete and query operations. To such sequences of operations are associated, for each data type, a specific continued fraction and a familly of orthogonal polynomials : Tchebycheff for stacks, Laguerre for dictionaries, Hermite for priority queues, Meixner for linear lists and Charlier for symbol tables. We define a notion of integrated cost of a data structure as the average cost over all possible sequences of operations. Our main result is an explicit expression, for each of these data structures, of the generating function for integrated costs as a linear integral transform of the generating functions for individual operation costs. We use the result to explicitly compute integrated costs of various efficient data structure implementations.

We introduce a notion of integrated cost of a dictionary, as average cost of sequences of search, insert and delete operations. We express generating functions of these sequences in terms of continued fractions; from this we derive an explicit integral expression of integrated costs for three common representations of dictionaries.

We present a new data-structure for representing priority queues, the pagoda. A detailed analysis shows that the pagoda provides a very efficient implementation of priority queues, where our measure of efficiency is the average run time of the various algorithms. It handles an arbitrary sequence of n primitive operations chosen from MIN, INSERT, UNION, EXTRACT and EXTRACTMIN in time o(n log n). The constant factors affecting these asymptotic run time are small enough to make the pagoda competitive with any other priority queue, including structures which cannot handle UNION or EXTRACT. The given algorithms process an arbitrary sequence of n operations MIN, INSERT and EXTRACT in linear average time O(n), and a sequence of n INSERT in linear worst case time O(n).