TOPICS
Search

Square Triangle Picking


Square triangle picking

Square triangle picking is the selection of triples of points (corresponding to endpoints of a triangle) randomly placed 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 at random 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 result 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)/(20746)
(9)
=0.004581....
(10)
SquareTrianglePickingDistribution

The distribution function for the area of a random triangle inscribed in a square is given exactly 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 corresponding distribution function is given by

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

(Philip).

P(A) satisfies the beautiful 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 beautiful formula for raw moments mu_n^' as

 mu_n^'=(3·2^(3-n)[(n+2)H_(n+1)+1])/((n+1)(n+2)^3(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/9000, 1/2400, 363/109760, ... (OEIS A093158 and A093159).

A closed form is more difficult to compute for the nth central moments 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 is expression is valid for 1/2<=x<1 and 1/2<=y<=x, with the expression over the whole unit square 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)

As expected, this expression satisfies

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

Pick three points at random 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).


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.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. n.d. 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. 2000. http://axchiv.org/abs/math.GM/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. http://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. http://www.mathematicaguidebooks.org/.Woolhouse, W. S. B. "Question 2471." Mathematical Questions, with Their Solutions, from the Educational Times, Vol. 8. London: 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 Web Resource. https://mathworld.wolfram.com/SquareTrianglePicking.html

Subject classifications