Home  About us  Contact
 

Random Trees (random + tree)

Distribution by Scientific Domains
Mathematics and Statistics87%

Selected Abstracts

Tactics-Based Behavioural Planning for Goal-Driven Rigid Body Control

COMPUTER GRAPHICS FORUM, Issue 8 2009
Stefan Zickler
Computer Graphics [I.3.7]: Animation-Artificial Intelligence; [I.2.8]: Plan execution, formation, and generation; Computer Graphics [I.3.5]: Physically based modelling Abstract Controlling rigid body dynamic simulations can pose a difficult challenge when constraints exist on the bodies' goal states and the sequence of intermediate states in the resulting animation. Manually adjusting individual rigid body control actions (forces and torques) can become a very labour-intensive and non-trivial task, especially if the domain includes a large number of bodies or if it requires complicated chains of inter-body collisions to achieve the desired goal state. Furthermore, there are some interactive applications that rely on rigid body models where no control guidance by a human animator can be offered at runtime, such as video games. In this work, we present techniques to automatically generate intelligent control actions for rigid body simulations. We introduce sampling-based motion planning methods that allow us to model goal-driven behaviour through the use of non-deterministic,Tactics,that consist of intelligent, sampling-based control-blocks, called,Skills. We introduce and compare two variations of a Tactics-driven planning algorithm, namely behavioural Kinodynamic Rapidly Exploring Random Trees (BK-RRT) and Behavioural Kinodynamic Balanced Growth Trees (BK-BGT). We show how our planner can be applied to automatically compute the control sequences for challenging physics-based domains and that is scalable to solve control problems involving several hundred interacting bodies, each carrying unique goal constraints. [source]

Random trees and general branching processes

RANDOM STRUCTURES AND ALGORITHMS, Issue 2 2007
Anna Rudas
Abstract We consider a tree that grows randomly in time. Each time a new vertex appears, it chooses exactly one of the existing vertices and attaches to it. The probability that the new vertex chooses vertex x is proportional to w(deg(x)), a weight function of the actual degree of x. The weight function w : , , ,+ is the parameter of the model. In 4 and 11 the authors derive the asymptotic degree distribution for a model that is equivalent to the special case, when the weight function is linear. The proof therein strongly relies on the linear choice of w. Using well-established results from the theory of general branching processes we give the asymptotical degree distribution for a wide range of weight functions. Moreover, we provide the asymptotic distribution of the tree itself as seen from a randomly selected vertex. The latter approach gives greater insight to the limiting structure of the tree. Our proof is robust and we believe that the method may be used to answer several other questions related to the model. It relies on the fact that considering the evolution of the random tree in continuous time, the process may be viewed as a general branching process, this way classical results can be applied. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007 [source]

On the shape of the fringe of various types of random trees

MATHEMATICAL METHODS IN THE APPLIED SCIENCES, Issue 10 2009
Michael Drmota
Abstract We analyze a fringe tree parameter w in a variety of settings, utilizing a variety of methods from the analysis of algorithms and data structures. Given a tree t and one of its leaves a, the w(t,,a) parameter denotes the number of internal nodes in the subtree rooted at a's father. The closely related w,(t,,a) parameter denotes the number of leaves, excluding a, in the subtree rooted at a's father. We define the cumulative w parameter as W(t) = ,aw(t,,a), i.e. as the sum of w(t,,a) over all leaves a of t. The w parameter not only plays an important rôle in the analysis of the Lempel,Ziv '77 data compression algorithm, but it is captivating from a combinatorial viewpoint too. In this report, we determine the asymptotic behavior of the w and W parameters on a variety of types of trees. In particular, we analyze simply generated trees, recursive trees, binary search trees, digital search trees, tries and Patricia tries. The final section of this report briefly summarizes and improves the previously known results about the w, parameter's behavior on tries and suffix trees, originally published in one author's thesis (see Analysis of the multiplicity matching parameter in suffix trees. Ph.D. Thesis, Purdue University, West Lafayette, IN, U.S.A., May 2005; Discrete Math. Theoret. Comput. Sci. 2005; AD:307,322; IEEE Trans. Inform. Theory 2007; 53:1799,1813). This survey of new results about the w parameter is very instructive since a variety of different combinatorial methods are used in tandem to carry out the analysis. Copyright © 2008 John Wiley & Sons, Ltd. [source]

The height of increasing trees

RANDOM STRUCTURES AND ALGORITHMS, Issue 4 2008
N. Broutin
Abstract We extend results about heights of random trees (Devroye, JACM 33 (1986) 489,498, SIAM J COMP 28 (1998) 409,432). In this paper, a general split tree model is considered in which the normalized subtree sizes of nodes converge in distribution. The height of these trees is shown to be in probability asymptotic to clog n for some constant c. We apply our results to obtain a law of large numbers for the height of all polynomial varieties of increasing trees (Bergeron et al. Lect Notes Comput Sci (1992) 24,48).© 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008 [source]

Level of nodes in increasing trees revisited

RANDOM STRUCTURES AND ALGORITHMS, Issue 2 2007
Alois Panholzer
Abstract Simply generated families of trees are described by the equation T(z) = ,(T(z)) for their generating function. If a tree has n nodes, we say that it is increasing if each node has a label , { 1,,,n}, no label occurs twice, and whenever we proceed from the root to a leaf, the labels are increasing. This leads to the concept of simple families of increasing trees. Three such families are especially important: recursive trees, heap ordered trees, and binary increasing trees. They belong to the subclass of very simple families of increasing trees, which can be characterized in 3 different ways. This paper contains results about these families as well as about polynomial families (the function ,(u) is just a polynomial). The random variable of interest is the level of the node (labelled) j, in random trees of size n , j. For very simple families, this is independent of n, and the limiting distribution is Gaussian. For polynomial families, we can prove this as well for j,n , , such that n , j is fixed. Additional results are also given. These results follow from the study of certain trivariate generating functions and Hwang's quasi power theorem. They unify and extend earlier results by Devroye, Mahmoud, and others. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007 [source]

Nodes of large degree in random trees and forests

RANDOM STRUCTURES AND ALGORITHMS, Issue 3 2006
Bernhard Gittenberger
We study the asymptotic behavior of the number Nk,n of nodes of given degree k in unlabeled random trees, when the tree size n and the node degree k both tend to infinity. It is shown that Nk,n is asymptotically normal if and asymptotically Poisson distributed if . If , then the distribution degenerates. The same holds for rooted, unlabeled trees and forests. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006 [source]