Barycentric coordinates
Geometric Probability
Let u, v, and w stand for the lengths of the three segments (one or two of them may be 0.) The three segments serve as the sides of a triangle iff
(1) |
x_{1} < x_{2} + x_{3} x_{2} < x_{1} + x_{3} x_{3} < x_{1} + x_{2} |
From the conditions of the problem, x_{1} + x_{2} + x_{2} = 1. To each of the inequalities in (1) add its left-hand side to obtain
(2) |
x_{1} < 1/2 x_{2} < 1/2 x_{3} < 1/2 |
The argument is obviously reversible. Therefore also, (2) implies (1). Let us consider the triple (u,v,w) as the barycentric coordinates of a point relative to some fixed triangle ABC. As we already know, points that satisfy (2) lie inside the triangle M_{a}M_{b}M_{c}, where M_{a}, M_{b}, M_{c} are the midpoints of the sides BC, AC, and AB, respectively. The area of the triangle M_{a}M_{b}M_{c} is one fourth that of ABC. Which shows that 1/4 is the sought probability.
The barycentric coordinates can be set up in a more general space R^{n}, n>0. For n=1, it takes 2 distinct points A and B and two coordinates u and v. Every point K on the line R^{1} is then uniquely represented as K = uA + vB with u + v = 1. In R^{3}, it takes 4 points. More generally, to define the barycentric coordinates in R^{n} one needs (n+1) points that do not lie in a space of a lesser dimension. For example, in R^{3}, four vertices of a (nondegenerate) tetrahedron define a set of barycentric coordinates. However, no four points in R^{3} that belong to the same plane (R^{2}) do; for 3>2!
For (n+1) points A_{i}, i = 0,...,n, the set of all points x_{0}A_{0} + ... + x_{n}A_{n} with x_{0} + ... + x_{n} = 1, is known as an n-dimensional simplex. So that respectively a segment is a 1-dimensional, a triangle is a 2-dimensional, and a tetrahedron is a 3-dimensional simplex. Simplexes play a fundamental role in Algebraic Topology.
Let's return to our problem. Choose n points at random on a segment of length 1. What is the probability that an (n+1)-gon (a polygon with (n+1) sides) can be constructed from the (n+1) thus obtained segments? Condition (1) generalizes to
(1') | x_{i} < x_{0} + ... + x_{n} - x_{i} = 1 - x_{i} |
for all i = 0, ..., n. Which is obviously equivalent to
(2') | x_{i} < 1/2, |
i = 0, ..., n. Generally speaking, areas change as the square of the linear size. Volumes change as the cube of the linear size. By analogy, bodies in R^{n} are endowed with the n-dimensional volume that changes as the n-th power of the linear size. The body described by (2') is obtained from the basic simplex by removing smaller simplexes, one at every vertex. Each of these (n+1) smaller simplexes has the n-volume equal to (1/2)^{n} of the n-volume of the basis simplex. Therefore, the probability that the barycentric coordinates of a point satisfy (2') is
(3) | p = 1 - (n+1)(1/2)^{n}, |
The latter expression tends to 1 as n grows to infinity. It is easier to find segments to construct a many sided polygon than it is to find the sides of a triangle, which is rather natural.
Reference
- J. Coffman, What To Solve?, Clarendon Press, Oxford, 1996. Fourth printing
|Contact| |Front page| |Contents| |Geometry| |Probability|
Copyright © 1996-2018 Alexander Bogomolny