TOPICS
Search

Square Triangle Picking

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
Square triangle picking

Square triangle picking is the independent uniform selection of triples of points (corresponding to vertices of a triangle) inside a square. n random triangles can be picked in a unit square in the Wolfram Language using the function RandomPoint[Rectangle[], {n, 3}].

Given three points chosen independently and uniformly inside a unit square, the average area of the triangle determined by these points is given analytically by the multiple integrals

A^_=(int_0^1int_0^1int_0^1int_0^1int_0^1int_0^1|Delta|dx_1dx_2dx_3dy_1dy_2dy_3)/(int_0^1int_0^1int_0^1int_0^1int_0^1int_0^1dx_1dx_2dx_3dy_1dy_2dy_3)
(1)
=int_0^1int_0^1int_0^1int_0^1int_0^1int_0^1|Delta|dx_1dx_2dx_3dy_1dy_2dy_3.
(2)

Here, (x_i,y_i) represent the polygon vertices of the triangle for i=1, 2, 3, and the (signed) area of these triangles is given by the determinant

Delta=1/(2!)|x_1 y_1 1; x_2 y_2 1; x_3 y_3 1|
(3)
=1/2(-x_2y_1+x_3y_1+x_1y_2-x_3y_2-x_1y_3+x_2y_3).
(4)

The solution was first given by Woolhouse (1867). Since attempting to do the integrals by brute force results in intractable integrands, the best approach using computer algebra is to divide the six-dimensional region of integration into subregions using cylindrical algebraic decomposition such that the sign of Delta does not change, do the integral in each region directly, and then combine the results (Trott 1998). Depending on the order in which the integration variables are ordered, between 32 and 4168 regions are obtained. The result of combining these pieces gives the mean triangle area

A^_=(11)/(144)
(5)

(Ambartzumian 1987, Pfiefer 1989, Trott 1998; Trott 2006, pp. 303-304).

Once A^_ is known, the variance in area is easily calculated by first computing the raw moment mu_2^'=<A^2>,

<A^2>=int_0^1int_0^1int_0^1int_0^1int_0^1int_0^1Delta^2dx_1dx_2dx_3dy_1dy_2dy_3
(6)
=1/(96),
(7)

giving

var(A)=<A^2>-A^_^2
(8)
=(95)/(20736)
(9)
=0.004581....
(10)
SquareTrianglePickingDistribution

The area distribution was obtained by Henze (1983). For 0<A<1/2, the probability density function for the area of a random triangle in the unit square is given by

P(A)=4[12(ln(2A)-5)ln(2A)A^2+24(A+1)Li_2(2A)A-4(A+1)pi^2A-6A+3(2A-1)(10A+1)ln(1-2A)+3]
(11)

(M. Trott, pers. comm., Jan. 27, 2005; Trott 2006, p. 306). The probability density function is zero outside [0,1/2]. The corresponding distribution function is given by

D(A)=-(16)/3[17-3ln(2A)]A^3ln(2A)+16(2A+3)[Li_2(2A)-1/6pi^2]A^2 +4/3(10-17A)A+2/3(1-2A)(1-16A-68A^2)ln(1-2A)
(12)

(Philip). The distribution function is 0 for A<=0 and 1 for A>=1/2.

P(A) satisfies the fourth-order ordinary differential equation

A^3(1-2A)P^('''')(A)+A^2P^(''')(A)-4A^2P^('')(A)+8AP^'(A) -8P(A)-96(2A-1)=0
(13)

(M. Trott, pers. comm., Jan. 27, 2005; Trott 2006, p. 307).

This gives the formula for raw moments mu_n^' as

mu_n^'=(3·2^(3-n)H_(n+2))/((n+1)(n+2)^2(n+3)^2),
(14)

where H_n is a harmonic number, so the raw moments for n=1, 2, ... are 11/144, 1/96, 137/72000, 1/2400, 363/3512320, ... (OEIS A093158 and A093159).

A closed form is more difficult to compute for the nth central moment mu_n, but the first few for n=1, 2, ... are 0, 95/20736, 75979/186624000, 1752451/17915904000, ... (OEIS A103281 and A103282; Trott 2006, p. 307).

SquareTrianglePickingPointDistribution

A closed form for the probability that a given point (x,y) lies within a randomly picked triangle can also be obtained as

P_0(x,y)=(f(x,y)(x-1)^2)/(2x(y-1)y)-3/2(6xy^2-4y^2-6xy+4y+2x-1)ln(1/x-1)(x-1)^2+3/2(2y-1)(2xy^2-2y^2-2xy+2y+2x-1)ln(1/y-1) ×(x-1)^2,
(15)

where

f(x,y)=12x^2y^4-30xy^4+3y^4-24x^2y^3+60xy^3-6y^3+25x^2y^2-43xy^2+4y^2-13x^2y+13xy-y+x^2-x
(16)

(M. Trott, pers. comm., Jan. 31, 2005; Trott 2006, p. 310). This expression is valid for 1/2<=x<1 and 1/2<=y<=x, with the expression for 0<x,y<1 given by symmetry as

P(x,y)={P_0(x,y) for 1/2<=x<1,1/2<=y<=x; P_0(x,1-y) for 1/2<=x<1, 1/2<=1-y<=x; P_0(1-y,x) for 1/2<=x<1, 0<y<=1-x; P_0(1-y,1-x) for 0<x<=1/2, 0<y<=x; P_0(1-x,1-y) for 0<x<=1/2, x<=y<=1/2; P_0(1-x,y) for 0<x<=1/2, x<=1-y<=1/2; P_0(y,1-x) for 0<x<=1/2, 0<1-y<=x; P_0(y,x) for 1/2<=x<1, 0<1-y<=1-x.
(17)

On the boundary of the unit square, P(x,y)=0. As expected, this expression satisfies

int_0^1int_0^1P(x,y)dxdy=(11)/(144).
(18)

Pick three points independently and uniformly in the unit square, and denote the probability that the three points form an obtuse triangle by Pi(2). Langford (1969) proved that

Pi(2)=(97)/(150)+1/(40)pi
(19)
=0.725206483...
(20)

(OEIS A093072).

An invertible affine transformation takes the unit square to any parallelogram and multiplies all areas by the same absolute value of its determinant. It also preserves independent uniform sampling after normalization. Thus, if a parallelogram has area S and A_S is the area of a triangle formed by three independent uniform points, A_S/S has the same distribution function as A. In particular,

<A_S>=(11S)/(144)
(21)
<A_S^2>=(S^2)/(96)
(22)
var(A_S)=(95S^2)/(20736).
(23)

The reduction applies to parallelograms, since they are precisely the affine images of a square. It does not reduce an arbitrary convex quadrilateral to the square case.

See also

Cube Tetrahedron Picking, Heilbronn Triangle Problem, Hexagon Triangle Picking, Obtuse Triangle, Polygon Triangle Picking, Square Line Picking, Sylvester's Four-Point Problem, Triangle Triangle Picking, Unit Square

Explore with Wolfram|Alpha

References

Alagar, V. S. "On the Distribution of a Random Triangle." J. Appl. Prob. 14, 284-297, 1977.Ambartzumian, R. V. (Ed.). Stochastic and Integral Geometry. Dordrecht, Netherlands: Reidel, 1987.Buchta, C. "Über die konvexe Hülle von Zufallspunkten in Eibereichen." Elem. Math. 38, 153-156, 1983.Buchta, C. "Zufallspolygone in konvexen Vielecken." J. reine angew. Math. 347, 212-220, 1984.Buchta, C. "Zufällige Polyeder-Eine Übersicht." In Zahlentheoretische Analysis: Wiener Seminarberichte 1980-82 (Ed. E. Hlawka). Berlin, Germany: Springer-Verlag, pp. 1-13, 1985.Finch, S. R. "Geometric Probability Constants." §8.1 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 479-484, 2003.Henze, N. "Random Triangles in Convex Regions." J. Appl. Prob. 20, 111-125, 1983.Klee, V. "What Is the Expected Volume of a Simplex Whose Vertices Are Chosen at Random from a Given Convex Body." Amer. Math. Monthly 76, 286-288, 1969.Langford, E. "The Probability That a Random Triangle Is Obtuse." Biometrika 56, 689-690, 1969.Pfiefer, R. E. "The Historical Development of J. J. Sylvester's Four Point Problem." Math. Mag. 62, 309-317, 1989.Philip, J. "The Area of a Random Convex Polygon." Tech. Report TRITA MAT 04 MA 07. http://www.math.kth.se/~johanph/area12.pdf.Santaló, L. A. Integral Geometry and Geometric Probability. Reading, MA: Addison-Wesley, 1976.Seidov, Z. F. "Letters: Random Triangle." Mathematica J. 7, 414, 2000.Seidov, Z. F. "Random Triangle Problem: Geometrical Approach." 16 Feb 2000. https://arxiv.org/abs/math/0002134.Sloane, N. J. A. Sequences A093072, A093158, A093159, A103281, and A103282 in "The On-Line Encyclopedia of Integer Sequences."Trott, M. "The Area of a Random Triangle." Mathematica J. 7, 189-198, 1998. https://library.wolfram.com/infocenter/Articles/3413/.Trott, M. "Area of a Random Triangle in a Square." §1.10.1 in The Mathematica GuideBook for Symbolics. New York: Springer-Verlag, pp. 298-311, 2006. https://www.mathematicaguidebooks.org/.Woolhouse, W. S. B. "Question 2471." Mathematical Questions, with Their Solutions, from the Educational Times, Vol. 8. London, England: F. Hodgson and Son, pp. 100-105, 1867.

Referenced on Wolfram|Alpha

Square Triangle Picking

Cite this as:

Weisstein, Eric W. "Square Triangle Picking." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SquareTrianglePicking.html

Subject classifications