Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-15T23:20:25.577Z Has data issue: false hasContentIssue false

On the total length of the random minimal directed spanning tree

Published online by Cambridge University Press:  01 July 2016

Mathew D. Penrose*
Affiliation:
University of Bath
Andrew R. Wade*
Affiliation:
University of Bath
*
∗ Postal address: Department of Mathematical Sciences, University of Bath, Bath BA2 7AY, UK.
∗ Postal address: Department of Mathematical Sciences, University of Bath, Bath BA2 7AY, UK.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

In Bhatt and Roy's minimal directed spanning tree construction for a random, partially ordered set of points in the unit square, all edges must respect the ‘coordinatewise’ partial order and there must be a directed path from each vertex to a minimal element. We study the asymptotic behaviour of the total length of this graph with power-weighted edges. The limiting distribution is given by the sum of a normal component away from the boundary plus a contribution introduced by the boundary effects, which can be characterized by a fixed-point equation, and is reminiscent of limits arising in the probabilistic analysis of certain algorithms. As the exponent of the power weighting increases, the distribution undergoes a phase transition from the normal contribution being dominant to the boundary effects being dominant. In the critical case in which the weight is simple Euclidean length, both effects contribute significantly to the limit law.

Information

Type
Stochastic Geometry and Statistical Applications
Copyright
Copyright © Applied Probability Trust 2006