Inside the Triangles
amcwill417
form the vertices of a triangle T. What is the probability that a new
fourth random point falls within T ? This appears to be equivalent to
asking for the mean value of all such Ts which I find to be close to 0.0763
(finite simulation for 10,000,000 trials). Can someone offer an analytical
solution?
Alex
amcwill417
"amcwill417" <amcwi...@email.msn.com> wrote in message
news:foCBc.412$%w1.1...@eagle.america.net...
Alex
Jim Dars
It was so nice to see a non-philosophical question on the board; and one
requiring a numerical answer at that!!
After a full five minutes thinking about what an approach might be I came up
with little. However, the following consideration might be worth some
further thought. The 3 points will have a highest x-value and a lowest
x-value. They will have a highest y-value and a lowest y-value. Use these
values to construct a rectangle about the triangle. Two possibilities
exist. All three points will be on the rectangular perimeter, or just two
points will be on the perimeter. In the later case they will be in diagonal
corners. In the former case one point will be in a corner (There is only
one middle value for x and one middle value for y, thus one point must carry
two extreme values.)
Now nothing is lost by orienting the rectangle so that the point in the
corner is placed at (0,0) so that two "rays" emanate into the first
quadrant, their ends being attached to form the triangle.
Now the two rays have a fixed angle between them, nothing is lost by letting
the longest ray be the upper ray.
Now nothing is lost by rotating the rays such that the shortest is on the
x-axis.
Then the triangle area is easy to calculate. The distribution of the length
of the rays, and the angle between is, of course, where the mathematical
problem exists.
Then again, this may turn out to be a stupid way to proceed.
Best wishes, Jim
amcwill417
"Jim Dars" <jim-...@comcast.net> wrote in message
news:68EBc.70030$Hg2.44442@attbi_s04...
The area of any triangle T can be calculated using Heron's formula which
yields the area in terms of the three sides and for any set of three random
points one can calculate the three sides of the triangle T from the known
coordinates of the points. The fourth point P will either be inside or
outside the triangle T. The three distances from P to the vertices of the
triangle T can be calculated. If P is inside the triangle T then the three
subtriangles formed by drawing lines from P to the vertices of the triangle
T should have a combined area equal to that of T. If P is outside T then
the combined area will be greater than that of T. So by calculating all the
distances and applying Heron's formula four times one can determine whether
or not P is inside T. By this means the simulation can count how many times
P is inside T and hence the probability results. Call this the TProb.
However, and more simply, the probability that the fourth point P is inside
T should depend only on the area of T which will be a fraction of the unit
square. Call this probability AProb. The simulation (i.e., Monte Carlo) for
TProb and the simulation for AProb yield the same result. I.e., 0.0763 and
0.0763. But all this is by computer simulation. It seems that an analytical
approach will involve some rather involved integrations or perhaps a very
simple insight leading to a shortcut. In this regard your remarks seem to
point to a way of setting up in a systemmatic manner such integrations.
Alex
Mark Spahn
(it elicited no response at all), which I will quote below.
Let's think more generally...
Any three (random) points in the unit square determine
(1) a quadratic equation y = ax^2+bx+c on which they all lie
(2) a circle on which they all lie
(3) a triangle whose vertices the points are
(4) some other curve or shape?
We can ask the probability that a fourth random point in the square will lie
(1) below the line y = ax^2+bx+c
(2) inside the circle
(3) inside the triangle.
Problem (1) is complicated by the fact that the quadratic curve
might loop outside the square and come back in.
Problem (2) is complicated by the many ways in which the
circle might overlap the square (or lie completely inside it).
Problem (3) might be easier than (1) and (2), because
the triangle is guaranteed to lie completely within the square.
To get a better grip on solving such probability problems analytically
(i.e., not by a computer simulation), let's consider the even simpler
Problem: Given two random points in the unit square,
what is the probability that a third random point will
lie below the line on which the first two points lie?
A symmetry argument says that this probability must be 1/2,
so we know what the answer is going to be. Let's try to
compute it analytically by determining the average proportion
of the square that lies below this random line. The line can
cross any two of the square's four sides, so it looks like we
have (4 pick 2) = 6 cases to consider.
I got sidetracked while considering this problem, but acmwill417
has inspired me to revisit it.
-- Mark Spahn
===== QUOTE OF EARLIER PROBLEM =====
PROBLEM:
What is the probability that a random point in the unit square
will lie within the circle that passes through three other
random points in the unit square?
DISCUSSION:
(This problem was prompted by (my original misreading of)
an earlier problem on this forum.)
Given any three points (x1,y1), (x2,y2), (x3,y3) that do not
lie in a straight line, there is a circle whose circumference
passes through all three points. A way to find the center
and radius of this circle is to observe that the line from
point 1 to point 2 is a chord of the circle, and so is the line from
point 1 to point 3. The perpendicular bisectors of these two
chords (like the perpendicular bisectors of any two chords of
a circle) will intersect at the the circle's center (xc,yc).
It is relatively easy to work out that the equation of the
perpendicular bisector of the line from (x1,y1) to (x2,y2) is
(x2-x1)x + (y2-y1)y = (1/2)[(x2-x1)(x2+x1) + (y2-y1)(y2+1)]
and the perpendicular bisector of the line from (x1,y1) to (x3,y3) is given
by
(x3-x1)x + (y3-y1)y = (1/2)[(x3-x1)(x3+x1) + (y3-y1)(y3+1)].
The center (xc,yc) of the circle is the solution of these
two simultaneous linear equations, which can be determined
by, for example, Cramer's Rule.
(If the three points are collinear, the determinant in the denominator,
| x2-x1 y2-y1 |
| x3-x1 y3-y1 |
will be equal to zero.)
Once the circle's center (xc,yc) is known, its radius is given by
the distance between the center and any of the three points:
r^2 = (x1-xc)^2 + (y1-yc)^2.
For example, the circle that passes through
(.060,.452), (.084,.570), (.929,.073) has its center
at (.55962,.41182) and has radius r=.50123.
Another example: the circle that passes through
(.42,.05), (.02,.51), (.20,.31) (nearly collinear) has its center
at (-7.304,-6.263) and radius r=9.9758.
Given three random points in the unit circle,
the probability that a fourth random point in the unit circle
will lie within the circle defined by the first three points
is equal to the proportion of the area of the unit circle
that lies within this circle.
So what this problem asks for is, in some sense,
the average proportion of the unit circle that is
covered by a circle whose circumference passes
through three random points in the unit circle.
I do not see how to calculate the asked-for probability.
It looks like it will involve a hairy integration to determine
a volume in six-dimensional space where the six parameters
x1,...,y3 range between 0 and 1.
Does anybody have some insight into how to solve this
problem analytically?
As a stopgap, I wrote a program for my programmable calculator.
On three runs of this program, the proportion of times a fourth
random point lies within the circle defined by three random points is
1344/2610 = .51494
1602/3118 = .51379
1621/3105 = .52206.
Book recommendation:
Paul J. Nahin, "Duelling Idiots and Other Probability Puzzlers"
This problem collection contains an insight (page 30-31) that
allowed me to figure out that the probability of having visited
every page of an m-page reference book after n random
lookups is approximated by 1 - m/exp(n/m).
Having, over the course of years, looked up words in a
2,066-page dictionary an estimated 20,440 times, the
probability that I have laid eyes on all of its pages is
1 - 2066/exp(20440/2066) = 89.57%.
-- Mark Spahn
===== UNQUOTE =====
Virgil
"Mark Spahn" <msp...@localnet.com> wrote:
"amcwill417" <amcwi...@email.msn.com> wrote in message
news:foCBc.412$%w1.1...@eagle.america.net...
> Three points are independently and randomly chosen within a unit
> square and form the vertices of a triangle T. What is the
> probability that a new fourth random point falls within T ?
Since the area of the triangle is 1, the probability that the fouth
point will fall within the the triangle equals the area of that triangle,
which is
[[ 1 x1 y1]
Area = (1/2)*abs(det( [1 x2 y2 ] ) )
[1 x3 y3 ]]
In The probability before any points are chose of the fourth point
falling in the triangle formed by the first 3 will be the Expected Value
of the triangular area. But I have no suggestions as to how to find that
expected value.
Jim Dars
Yes, I was aware of the formula. While that makes the simulation straight
forward it doesn't, to me, lend an idea as to the distribution of the area.
Denoting s_(i) be the i-th order statistic for the variable s then I can
find the distribution of
x_(3), x_(1) and hence [x_(3) - x_(1)].
Likewise for y.
For example, since I can find the distribution of
u = x_(3) - x_(1) and
v = y_(3) - y_(1) then I might be able to find the distribution of u*v,
namely the area of the rectangle. Then if I knew the distribution of the
area of the rectangle such a triangle takes up I could find a closed form
answer, if I could integrate (of course). While this sounds rather brutal,
and probably is, it would be one way to find the "analytical result" you
requested.
Best wishes, Jim (PS The Expected length of u and v is 1/3. Thus, all
this seems to be in the ballpark. You might do a simulation of the ratio of
the area of the triangle to that of the rectangle. If it is some "round"
number, like 1/2 or 1/3, then this would guide toward a "logical
mathematical" argument as to why this is so. I suspect I can find the
distribution of u*v if I had to.)
amcwill417
"Mark Spahn" <msp...@localnet.com> wrote in message
news:10dfdpd...@corp.supernews.com...
do not recall your original posting - most likely because I did not get into
it. You have inspired me to MAYBE simulate the other cases. I say MAYBE
because one must ration one's time. It is nice to get a numerical answer no
matter what the means.
Alex
amcwill417
Hi Mark,
Of the three problems, my simulation of (3) gives the probability = 0.0764,
as stated earlier. This triangle problem (3) appears more interesting to
me - for varous reasons, and problem (1) is of least interest. However I
may work on a simulation of (1) and start another thread for this in the
future unless someone else does it first.
Alex
amcwill417
> news:eWNBc.464$%w1.1...@eagle.america.net...
> >
> (it elicited no response at all), which I will quote below.
>
> Let's think more generally...
> Any three (random) points in the unit square determine
> (1) a quadratic equation y = ax^2+bx+c on which they all lie
> (2) a circle on which they all lie
> (3) a triangle whose vertices the points are
> (4) some other curve or shape?
>
> We can ask the probability that a fourth random point in the square will
lie
> (1) below the line y = ax^2+bx+c
> (2) inside the circle
> (3) inside the triangle.
>
After a little reflection it seems rather obvious that the answer to problem
(1) is the prob = 1/2. Why? By symmetry.
Alex
amcwill417
reflection makes it obvious that by symmetry (of many trials) the prob for
(3) is 1/2.
Alex
Mark Spahn
Hi Alex,
Yeah, come to think of it, I think you're right.
Given three random points p1, p2, p3 in the unit square,
consider the three points p1', p2', p3', which are reflections
of the first three points about the line y = 1/2.
The area in the square that lies below the
quadratic curve through p1, p2, p3, is equal to
the area in the square that lies above the
quadratic curve through p1', p2', p3'.
(The two quadratic curves are mirror-images
of each other about the line y = 1/2.)
The areas in the square below the two curves add up to 1.
Since the probability of each set of three points
is the same, their average below-the-curve area is 1/2.
Next step: Write a quick simulation of this problem.
If the answer from the simulation is not close to 1/2,
we did something wrong.
-- Mark
amcwill417
the square from above with a minimum near the square's center. The infinite
upper portion of the curve intercepts the top of the square at, say, x = 0.3
and x = 0.7. Now, any fourth point in the square and below the curve will
also be below the curve at, say, x = 0.1 even though the curve is not inside
the square at x = 0.1. So.... when you say the fourth point is below the
curve do you mean, in this special case, the above or do you mean only
between x = 0.3 and x = 0.7? That is to say, only in that x-range where the
curve is inside the square?
Alex
Mark Spahn
Alex,
We are asking for the probability that a fourth random point
*in the unit square* lies below the curve y = ax^2+bx+c defined
by three random points in the unit square. In the curve you mention
-- a concave-upward curve that has its minimum near (0.5,0.5)
and cuts the line y=1 at x=0.3 and x=0.7 -- any point in the
unit square where x < 0.3 or x > 0.7 lies below this curve.
For this curve, the area in the unit square below the curve
is the area of the unit square (= 1), minus the area in the unit
square that lies above the curve (= integral of (1 - (ax^2+bx+c))
from x=0.3 to x=0.7).
Here's an even more extreme quadratic curve: the quadratic
curve that passes through the three points (.920,.866),
(.864,.951),(.824,.166) is y = -220.0x^2 + 391.4x -172.8.
This curve bulges upward (is concave downward),
is long and skinny, and overlaps the unit square.
It has its maximum at
x = -b/(2a) = .889, y = 1.084 (above the unit square),
cuts y=0 at x = .8185 and x = .9585, and
cuts y=1 at x = .8691 and x = .9081.
Since I last wrote, I did a simulation of the quadratic curve
problem. In each iteration, I picked three random points
in the unit square, determined the curve y=ax^2+bx+c that
passes through all three points, then got a fourth random
point in the unit square and counted whether it lies below
the curve. In a simulation that lasted 11 hours, in 2,707 of
5,364 such experiments, the fourth random point lay below
the curve; 2,707/5,364 = 0.50466 lies close enough to the
theoretical value of 1/2 that I am satisfied that nothing is
drastically wrong.
But I have grown suspicious of the symmetry argument itself.
Given three random points p1,p2,p3, we define a quadratic curve c
that passes through all three points. With each such triplet
of random points p1,p2,p3 in the unit square, we associated
in a one-to-one way the triplet of points p1',p2',p3' in the
unit square where p1',p2',p3' are the mirror images of p1,p2,p3 about
the line y=1/2. The resulting quadratic curve c' is the
mirror image of curve c reflected about the line y=1/2 and has the
property that the area of the part of the unit square that
lies below curve c, plus the area of the part of the unit
square that lies below curve c', adds up to 1 (the area
of the entire unit square).
So what? Earlier, I concluded from this fact that the
average of the area of the unit square that lies below
a quadratic curve is half of area 1, but I find it difficult
to justify this conclusion.
Consider problem (2): Find the probability that a fourth random
point in the unit square will lies inside the circle O defined by
three random points in the unit square, that is, the circle
on whose circumference all three points lie. For each such
triplet p1,p2,p3, we can find another triplet p1',p2',p3'
of points in the unit square such that the area of the
unit square inside their circle O', plus the area of the
unit square inside circle O, adds up to area 1.
(This is because given any area A between 0 and 1,
we can define a circle such that the overlap between
the unit circle and the circle has area A; for p1',p2',p3',
just take any three points on the circumference of the
circle that lie within the unit square.)
Are we justified in concluding from this that the
average area of the unit square inside a circle
defined by three random points in the unit square
is 1/2? For what it's worth, my simulation of this
problem does find a probability near 1/2.
-- Mark
amcwill417
Each run had 1,000,000 trials and each run lasted 2.5 minutes.. Don't have
time now to read all of your above message but will do so tomorrow. (For
single trials my simulation also plots the curve y = ax^2 + bx + c and shows
the locations of the four points so I know it is working correctly).
Alex
Mark Spahn
> O.K. My simulation yields for 4 runs 0.5021, 0.5015, 0.4975 and 0.4999.
> Each run had 1,000,000 trials and each run lasted 2.5 minutes.. Don't
have
> time now to read all of your above message but will do so tomorrow. (For
> single trials my simulation also plots the curve y = ax^2 + bx + c and
shows
> the locations of the four points so I know it is working correctly).
>
> Alex
>
Wow. My simulation, run on a programmable calculator bought in 1974
that was the latest whiz-bang technology of its day, takes 7.2 seconds
per trial, versus your 150 seconds/million trials. Your simulation is
48,000 times faster than mine.
I am in the midst of writing a program to determine, given three
random points in the unit square, the area in the unit square
that lies below the quadratic curve y = ax^2+bx+c that passes
through all three points. This area gives the actual probability
that, for the given three random points in the unit square,
a fourth random point in the unit squre will lie below the curve
-- not just the result of a single experiment with this curve.
This area ranges between 0 and 1, but I wonder how it is distributed.
If we ran a million trials and computed the area for each trial,
how many trials would have an area in each sub-range
0-.05, .05-.10, .10-.15, ..., .95-1?
Would all the sub-ranges be approximately equally populous,
or would the distribution look like a bell curve, much more
populous in .50-.55 than in, say, .85-.90?
There are a number of ways in which the quadratic curve
might overlap with the unit square, but I think I see some
simplifications that can be made. If I get the algorithm written,
I'll probably post it here (in pseudo-code), so that you --
or anyone else that wants to try -- can just copy my
algorithm rather than starting from scratch.
-- Mark
Mark Spahn
"Mark Spahn" <msp...@localnet.com> wrote in message news:...
Alex,
Oh, here's another thought. You already have a way to
find the area of a triangle whose vertices are three random
points in the unit square: Find the three sides a, b, c by
the Pythagorean theorem, then find the area by Heron's
rule: Area = sqrt(s(s-a)(s-b)(s-c)), where s = (1/2)(a+b+c)
is the triangle's semiperimeter. Offhand, I don't know how
big this triangle area can be, but it would probably be easy
for you to find the area of 1,000,000 such triangles and
jinn up a histogram showing how many trials produce a
triangle whose area is in each range 0-.05, .05-.10, ... .
-- Mark
amcwill417
Yes, it will be fairly easy to produce such data and I will do so soon and
post it..
Alex
amcwill417
My programming is done in Visual Basic. My work computer is an HP Pavilion
with Intel 533 MHz processor. By today's standards it is somewhat slow..
Alex
Macavity
Hi Alex, Jim and all,
The analytical answer is 11/144. Unfortunately not aware of any
elegant method.
Do check http://mathworld.wolfram.com/SquareTrianglePicking.html
where there are links for other shapes as well.
HTH.
Macavity
<mxy...@hotmail.ignore.com> wrote:
>
>Hi Alex, Jim and all,
>
>The analytical answer is 11/144. Unfortunately not aware of any
>elegant method.
>
You can check for yourself by integrating the absolute value of
1 | x1 y1 1 |
--- | x2 y2 1 |
2 | x3 y3 1 |
where each xi, yi vary in (0, 1). This is ugly, but can be done using
a good computer algebra package - I used Derive, bit down the terror
and kept integrating...
amcwill417
Here are results for the triangle areas for 10,000,000 trials::
0.00-0.05 4,526,911
0.05-0.10 2,594,604
0.10-0.15 1,450,672
0.15-0.20 780,056
0.20-0.25 391,867
0.25-0.30 172,251
0.30-0.35 62,705
0.35-0.40 17,779
0.40-0.45 3,030
0.45-0.50 125
0.50-0.55 0
0.55-0.60 0
Alex
amcwill417
"Macavity" <mxy...@hotmail.ignore.com> wrote in message
news:b6115760904dd6c0...@news.teranews.com...
Hi Macavity, Mark, Jim,
11/144 !!!!!!!!! Wow!!! I find it rather surprising that this turns out to
be a rational number. There has to be some simple insight about all this.
This rational has the form n/(n+1)^2 which looks nice - by why 11?
Alex
Mark Spahn
a square can have an area greater than half the square.
But seeing this result leads to the thought that
the subranges are too wide. What would the histogram look
like if you used subranges whose width is .01 rather than .05?
Would there be a hump somewhere? That is, is the most populous
subrange the leftmost one? Does the distribution look like a
bell-shaped curve that reaches it peak at, say, 0.03?
I presume it would be easy for you to display the results in
a bargraph, something like
0.00-0.01 ******************************
0.01-0.02 *************************************
0.02-0.03 *******************************************
0.03-0.04 *****************************************
etc.
And thanks to Macavity for the reference
http://mathworld.wolfram.com/SquareTrianglePicking.html
which gives the analytical answer to this triangle-in-square problem.
In working further on the quadratic curve problem, I find it is
a bit more complex than I anticipated. Looking only at
concave-upward quadratic curves y(x) = ax^2+bx+c
(i.e., where a>0), the lesser x where y(x)=1, the greater x
where y(x)=1, the lesser x where y(x)=0, and the greater x
where y(x)=0 can each either (1) lie in the range 0-1 or
(2) lie outside the range 0-1 (or not cut the line y=1 or y=0).
This yields 16 yes/no combinations, some of which are impossible.
For each curve, I will compute the area A under the curve,
and take statistics (average, standard deviation). It will be
a real challenge to shorten the program to the 256-step
capacity of my Casio FX-502P programmable calculator.
-- Mark
Rainer Rosenthal
"amcwill417" wrote
>
> Hi Macavity, Mark, Jim,
>
> 11/144 !!!!!!!!! Wow!!! I find it rather surprising that
> this turns out to be a rational number. There has to be
> some simple insight about all this. This rational has the
> form n/(n+1)^2 which looks nice - by why 11?
>
Greetings from the geometric AHA-threads :-))
And a big hand for Macavity! (No, I don't know what you are
talking about but I can hear the sound).
Greetings
Rainer Rosenthal
r.ros...@web.de
Earl Paddon
Hi, all
Think instead about 144, which equals 12 squared, and 1/12 is the
variance of a uniformly distribued varianble in the unit range.
Earl
Macavity
wrote:
This appears too deep for me - will think a bit more, but is there
something beyond a coincidence here?
Perplexed!
Earl Paddon
Okay - Look at it this way. The expected value of the square of the triangle
area is easily shown to be 3/2*sig^4, where sig^2=1/12
Then, the mean value of the area could be written sig^2-sig^4
I didn't try to solve the multidimensional mean value, as was done in the
Matmatica article, but my guess is this is no coincidence.
Earl
amcwill417
Hi All,
The probability for any one of the triangles to have an area which is a
rational number appears to be zero. So one might expect that the mean would
also be irrational - (although this does not exclude a rational mean). So
the number 11/144 came as a surprise to me.
Alex
amcwill417
Hi Mark,
Here is graph for 2 million trials and triangle areas in 0.01 intervals:
2 million trials
************************************* 0 223888
********************************* 0.01 200154
****************************** 0.02 180988
************************** 0.03 158356
*********************** 0.04 142744
********************* 0.05 127489
******************* 0.06 115017
***************** 0.07 102427
*************** 0.08 92259
************* 0.09 82359
************ 0.1 72478
********** 0.11 64109
********* 0.12 57214
******** 0.13 51130
******* 0.14 44192
****** 0.15 39839
***** 0.16 35722
***** 0.17 30875
**** 0.18 26223
*** 0.19 23918
*** 0.2 20578
** 0.21 17264
** 0.22 15335
** 0.23 13063
* 0.24 11299
* 0.25 9370
* 0.26 8197
* 0.27 6343
0.28 5704
0.29 4982
0.3 3641
0.31 2852
0.32 2309
0.33 2019
0.34 1743
0.35 1162
0.36 814
0.37 584
0.38 483
0.39 292
0.4 284
0.41 78
0.42 77
0.43 91
0.44 31
0.45 24
0.46 0
0.47 0
0.48 0
0.49 0
0.5 0
Alex
Mark Spahn
Thanks, Alex, for this result. So it looks like this distribution
is not a bell-shaped curve (there's no hump, but rather
the chopped-off upper tail of a bell-shaped curve. Interesting.
My little program on this problem produced, after 2,801
trials, the three random points (.9364432306,.2581062274),
(.01122200988,.2178792178), (.3572990964,.2329260476),
which yield a nearly collinear triangle having side lengths of
a = .9260953080
b = .5796912709
c = .3464040370
b+c = .9260953079, which means that (s-a) = (1/2)(b+c-a)
= -.00000000005 < 0, no doubt due to roundoff error.
So in computing the Area = sqrt[s(s-a)(s-b)(s-c)]
I inserted an "absolute value" instruction, lest an
almost-zero quantity in the brackets be negative.
The statistics I got for a run of n = 1500 trials was
mean Area = 0.7583632760 (the true answer is
reported to be 11/144 = 0.7638888), with standard
deviations <sigma>_n-1_ = .06660100133
and <sigma>_n_ = .06657879729,
but I don't know whether these standard deviations
have any meaning for a distribution that does not
look like a normal bell-shaped curve.
I have concluded that the 256-step capacity of my
programmable calculator is not big enough to handle
the problem of finding the average area beneath
the quadratic curve y(x) = ax^2+bx+c that passes
through three random points in the unit square.
(If only I had another 256 steps to play with!)
-- Mark
Virgil
"amcwill417" <amcwi...@email.msn.com> wrote:
> Hi All,
>
> The probability for any one of the triangles to have an area which is a
> rational number appears to be zero. So one might expect that the mean would
> also be irrational - (although this does not exclude a rational mean). So
> the number 11/144 came as a surprise to me.
>
> Alex
As far as that goes, the probability of getting a constructable number
(i.e., one that it is at least theoretically possible to approximate to
any desired degree of accuracy) also appears to be zero, but, low and
behold, all of the numbers we actually get seem to be among those
impossibly rare constructable numbers. How can that be?
Mike Terry
>
> I have concluded that the 256-step capacity of my
> programmable calculator is not big enough to handle
> the problem of finding the average area beneath
> the quadratic curve y(x) = ax^2+bx+c that passes
> through three random points in the unit square.
> (If only I had another 256 steps to play with!)
>
> -- Mark
>
>
Lucky we know that the answer is 1/2 by symmetry then! :)
Mike.
Earl Paddon
Hi All,
I just now ran a modified simulation of the random triangle with a
small
change - I used normal random variables(zero mean and unit variance)
for the x and y coordinates of each point. as expected, the root mean
square of the area
came out to be nearly 1.5 (1.49989), and the mean area was .865946,
the
std. deviation was .86604
It doesn't seem coincidence that both the mean and std. deviation are
sqrt(3)/2
within the limits of simulation accuracy.
Earl
point.
amcwill417
11/144 = 0.07639 and not 0.7369 as you state above.
Alex
Mark Spahn
> > The statistics I got for a run of n = 1500 trials was
> > mean Area = 0.7583632760 (the true answer is
> > reported to be 11/144 = 0.7638888), with standard
> > deviations <sigma>_n-1_ = .06660100133
> > and <sigma>_n_ = .06657879729,
> > but I don't know whether these standard deviations
> > have any meaning for a distribution that does not
> > look like a normal bell-shaped curve.
> >
> > I have concluded that the 256-step capacity of my
> > programmable calculator is not big enough to handle
> > the problem of finding the average area beneath
> > the quadratic curve y(x) = ax^2+bx+c that passes
> > through three random points in the unit square.
> > (If only I had another 256 steps to play with!)
> >
> > -- Mark
> >
> Hi Mark,
>
> 11/144 = 0.07639 and not 0.7369 as you state above.
>
> Alex
>
copying the numbers from my notebook.
The area my simulation got was .07583632760, and the
true area is 11/144 = .076388888888888888888... .
A later simulation (it's been running night and day)
of 10,930 trials (5 seconds per trial) finds a mean area of
.07625932034, with standard deviation of about .0675.
I think I'm about done with this problem, but here's
another one I thought of:
Any pair of random points defines a line segment.
Given two pairs of random points in the unit square,
what is the probability that their line segments
will cross each other, forming an X?
I suppose we could call this the "Probability of X" problem.
(And with three random line segments we would have a
"Probability of A" problem if they formed a triangle, or a
"Probability of H" problem if one line segment crossed the
other two. Any more patterns with three straight lines?)
-- Mark
Virgil
"Mark Spahn" <msp...@localnet.com> wrote:
> The statistics I got for a run of n = 1500 trials was
> mean Area = 0.7583632760 (the true answer is
> reported to be 11/144 = 0.7638888),
I get 11/144 ~= 0.0763888..., only a tenth of your value.
Mark Spahn
"the signed area" of the triangle having vertices at the three points
(x1,y1), (x2,y2), (x3,y3). How can a geometric figure have a
"signed" area, that is, an area that might be negative?
(I note that what is integrated is the absolute value of this
possibly negative "area".)
To find the area of this triangle as a function of these six numbers
x1,x2,x3,y1,y2,y3, we can find the triangles three sides a,b,c by
a = sqrt[(x1-x2)^2+(y1-y2)^2], b = ..., c = ..., then by Heron's rule
get the area as A=sqrt[s(s-a)(s-b)(s-c)], where s is the triangle's
semiperimeter s = (1/2)(a+b+c). In terms of the six coordinates,
this is a very complicated expression for A, but A is never negative.
The website http://mathworld.wolfram.com/TriangleArea.html
seems to say that the area of the triangle having vertices at
(x1,y1), (x2,y2), (x3,y3) is equal to
(1/2)|-x2y1+x3y1+x1y2-x3y2-x1y3+x2y3|
(where "|...|" means absolute value). Is this true?
Computationally, this is much simpler and faster than Heron's rule.
So why have I never before heard of this? Why isn't this expression
as famous as Heron's rule? Can someone please explain this?
Where does the above determinant expression come from?
That is, how does one prove that this expression gives a triangle's area?
-- Mark
Lynn Kurtz
wrote:
>The website http://mathworld.wolfram.com/TriangleArea.html
>seems to say that the area of the triangle having vertices at
>(x1,y1), (x2,y2), (x3,y3) is equal to
>(1/2)|-x2y1+x3y1+x1y2-x3y2-x1y3+x2y3|
>(where "|...|" means absolute value). Is this true?
>
>Computationally, this is much simpler and faster than Heron's rule.
>So why have I never before heard of this? Why isn't this expression
>as famous as Heron's rule? Can someone please explain this?
>Where does the above determinant expression come from?
>That is, how does one prove that this expression gives a triangle's area?
>
>-- Mark
>
Actually, this is a special case a the 3D result, although you need to
know a little about vectors to understand it. Let A, B, C be any three
points in 3D space. Form vectors for two sides, u = AB, v = AC. Then
the magnitude of the cross product of u and v is:
|u cross v| = |u||v|sin(theta) where theta is the angle between u and
v.
But this is just the area of the parallelogram formed by the two side
vectors u and v, and half this amount is the area of the triangle.
Cross products are easy to calculate, and in the special case the
triangle lies in the xy plane the vector u cross v is perpendicular to
that plane, and half its length gives the determinant formula.
--Lynn
amcwill417
"Virgil" <ITSnetNOTcom/vir...@COMCAST.com> wrote in message
news:ITSnetNOTcom/virgil-F85856.23161229062004@[63.218.45.211]...
Did not anything like 11/144. This answer seems so "simple" that one might
expect a simple solution using a simple approach by a simple person like me
: )
amcwill417
Example: two intersect while the third intersects none.
Example: none intersect but the angle between any two is less than, say, 20
degrees.
Example: length of one is, say, twice the length of another which is twice
the length of the third.
And so on.
Alex
Macavity
Have been trying to post a simple approach (apart from Earl's, which I
am still struggling with) - somehow my posts in the last two days seem
to vanish!
Reposted, with some more detail to pardon any multiplicity.
================================================================
Adapted from an article at:
http://www.math.kth.se/~johanph/area.pdf
WLOG, let (xi, yi) represent the points for i = 1, 2, 3. with
x1 < x2 < x3.
Construct the smallest rectangle R (sides parallel to the axes) around
the random triangle. There are essentially two distinct cases for our
purpose which cover all the possibilities:
Case 1: when the vertices of the triangle are all on the rectangle.
e.g. orientation (scaled and rotated to the unit square.)
+-----------+--------------------+
| 2 (s, 1) |
| |
| |
| |
| |
| |
| |
| (1, r) 3 +
| |
| |
| |
| |
1 +--------------------------------+
(0, 0)
Case 2: when one vertex of the triangle is inside the rectangle.
e.g. orientation (scaled and rotated to the unit square.)
+--------------------------------+ 3 (1, 1)
| |
| |
| |
| |
| |
| |
| |
| |
| |
| 2(r,s) |
| |
1 +--------------------------------+
(0, 0)
Case 2 happens iff y1 < y2 < y3, or y1 > y2 > y3. (which is 2 out of
3! ways to arrange the yi) or with 1/3 probability. Clearly, case 1
probability is 2/3.
Now, the determine the expected area of the rectangle, say E(R).
Clearly, E(x3 - x1) = 1/2, and similarly, the expected value of the
range in y coordinates is also 1/2. So E(R) = 1/4.
The last step is to determine the proportion of the rectangle expected
to be taken up by the triangle in each case. We can consider the same
question for a square, with appropriate rotation of the triangle , as
the transformation will not change area proportions. (Refer to the
figures). Thus
Case 1: Let A1 be the area occupied by the triangle
(0,0), (1, r), (s, 1), where r and s are in U(0, 1).
Then A1 = (1 - rs)/2 and
E(A1) = 3/8
Case 2: Let A2 be the area occupied by the triangle
(0, 0), (1, 1), (r, s), where r and s are in U(0, 1)
Then A2 = |s - r|/2 and
E(A2) = 1/6.
Thus the expected area of the random triangle is
= 2/3 E(R) E(A1) + 1/3 E(R) E(A2)
= 2/3 * 1/4 * 3/8 + 1/3 * 1/4 * 1/6
= 11/144.
Ken Pledger
"Mark Spahn" <msp...@localnet.com> wrote:
> "Macavity" <mxy...@hotmail.ignore.com> wrote in message
> news:e74273bd959db215...@news.teranews.com...
> > ....
> > You can check for yourself by integrating the absolute value of
> >
> > 1 | x1 y1 1 |
> > --- | x2 y2 1 |
> > 2 | x3 y3 1 |
> >
> > ....
> The above website says that the above determinant expression is
> "the signed area" of the triangle having vertices at the three points
> (x1,y1), (x2,y2), (x3,y3). How can a geometric figure have a
> "signed" area, that is, an area that might be negative?
> (I note that what is integrated is the absolute value of this
> possibly negative "area".)
It's purely a matter of convenience in a definition.
In a different context, you're probably used to integrating to
find the area "under" a curve, but if the curve is below the x-axis you
know that the area is regarded as negative.
In using determinants to find area, you get a sign depending on
which way you go around the boundary: anticlockwise (positive) or
clockwise (negative). You may like to see how the above determinant
formula works on the simple triangle with vertices (0,0), (1,0), (0,1),
and then with vertices (0,0), (0,1), (1,0).
>
> To find the area of this triangle as a function of these six numbers
> x1,x2,x3,y1,y2,y3, we can find the triangles three sides a,b,c by
> a = sqrt[(x1-x2)^2+(y1-y2)^2], b = ..., c = ..., then by Heron's rule
> get the area as A=sqrt[s(s-a)(s-b)(s-c)], where s is the triangle's
> semiperimeter s = (1/2)(a+b+c). In terms of the six coordinates,
> this is a very complicated expression for A, but A is never negative.
>
> The website http://mathworld.wolfram.com/TriangleArea.html
> seems to say that the area of the triangle having vertices at
> (x1,y1), (x2,y2), (x3,y3) is equal to
> (1/2)|-x2y1+x3y1+x1y2-x3y2-x1y3+x2y3|
> (where "|...|" means absolute value). Is this true?
Expand the above determinant and see.
>
> Computationally, this is much simpler and faster than Heron's rule.
If you're given the coordinates of the three vertices, yes. But
if you're given the lengths of the three sides, no. The more strings to
your bow, the better. :-)
> ....
> Where does the above determinant expression come from?
> That is, how does one prove that this expression gives
> a triangle's area?....
This is proved in many text-books on coordinate geometry. In fact
it's a special case of an n-dimensional formula using an nth-order
determinant with a factor 1/(n!) in front. You may like to think
about the three-dimensional version, giving the signed volume of a
tetrahedron.
Ken Pledger.
Mark Spahn
"Ken Pledger" <Ken.P...@mcs.vuw.ac.nz> wrote in message
news:Ken.Pledger-ED29...@bats.mcs.vuw.ac.nz...
Sorry, I wasn't clear. I know the determinate expands to the expression,
but I want to know why the determinate gives the area of the triangle.
>
> >
> > Computationally, this is much simpler and faster than Heron's rule.
>
>
> If you're given the coordinates of the three vertices, yes. But
> if you're given the lengths of the three sides, no. The more strings to
> your bow, the better. :-)
>
>
> > ....
> > Where does the above determinant expression come from?
> > That is, how does one prove that this expression gives
> > a triangle's area?....
>
>
> This is proved in many text-books on coordinate geometry. In fact
> it's a special case of an n-dimensional formula using an nth-order
> determinant with a factor 1/(n!) in front. You may like to think
> about the three-dimensional version, giving the signed volume of a
> tetrahedron.
>
> Ken Pledger.
Ken,
Thanks for your note. Here is what I have been thinking
today about this problem...
Given the sides a, b, c of a triangle, its area is given by
(1) A = sqrt[(a+b+c)(-a+b+c)(a-b+c)(a+b-c)]/4.
Given a triangle's vertices (x1,y1), (x2,y2), (x3,y3), its area is
(2) A = |(x1*y2-x2*y1)-(x1*y3-x3*y1)+(x2*y3-x3*y2)|/2.
Formula (1) has a name, "Heron's rule", and is famous;
it is taught in high school.
Formula (2) has no name, and is not well known
(at least, I never heard of it until a few days ago);
it is not taught in high school. Why?
Formula (1) was known to the ancient Greeks.
When did formula (2) first become known?
I imagine it was soon after Rene Decartes invented
Cartesian coordinates in the 1600's. Maybe it was
discovered by chance, before any theory of vectors
and cross products was developed. If anyone knows,
please let us know.
In Serway's textbook "Physics for Scientists and Engineers" (p. 310-11),
the cross product A x B of three-dimensional vectors
A=(xA,yA,zA) and B=(xB,yB,zB) is defined to be the
vector, in a direction given by a "right-hand rule", that has the
magnitude (length) |A||B|sin <theta>, where <theta> is
the angle from vector A to vector B (0 < <theta> < 180 degrees).
Serway asserts that A x B is given by the determinant
| i j k |
| xA yA zA|
| xB yB zB |.
If this assertion is true, then formula (2) holds for any three
points (x1,y1,0), (x2,y2,0), (x3,y3,0) in the xy plane.
But I do not see why the magnitide of the above
determinant is equal to |A||B|sin <theta>.
Does Serway omit this proof because it would be too
lengthy for a physics textbook, or because it is should
be obvious?
Anyway, thanks for the tip to look in coordinate geometry
textbooks for this proof.
-- Mark Spahn
Macavity
wrote:
>> > Where does the above determinant expression come from?
>> > That is, how does one prove that this expression gives
>> > a triangle's area?....
>>
>>
Will try to help you here:
Let vectors P1, P2, P3 be the vertices of the triangle you want to
measure. I shall use the following:
Area = 1/2 * Base * Altitude
WLOG, let |P1 - P2| be the Base.
The altitude must be perpendicular to P1 - P2. The direction of the
altitude is thus given as
(y1-y2) i - (x1-x2) j
The Altitude will now be the projection of P3 - P1 onto this
direction. So Altitude
| (x3 - x1)(y1 - y2) - (y3 - y1)(x1 - x2)|
= ----------------------------------------------
| P1 - P2 |
Hence Area = 1/2 * | (x3 - x1)(y1 - y2) - (y3 - y1)(x1 - x2)|
= 1/2 |x1 (y2 - y3) - x2 (y1 - y3) + x3 (y1 - y2))|
Which is represented by the determininant referred to.
HTH.
Mark Spahn
Thanks, Macavity, for this explanation.
I actually found a similar explanation in the "Analytic geometry"
article in the McGraw-Hill Encyclopedia of Science and Technology
(vol. 1, page 517), but your explanation is clearer.
I'm still blown away by the fact that this formula for the
computing area of a triangle from its vertex coordinates
is not well known, and I wonder whether this obscurity is
due to the fact that -- unlike Heron's Rule for a similar
formula for computing the area of a triangle from the lengths
of its sides -- it doesn't have a name.
Maybe it will become better known if we give it a name like
"Decartes's Rule".
-- Mark Spahn
amcwill417
"Macavity" <mxy...@hotmail.com> wrote in message
news:bb479608.04070...@posting.google.com...
Hi Macavity and All,
A very nice and technically simple derivation for 11/144. Thanks for
presenting this in such detailed and elegant fashion.
Alex
Virgil
"Mark Spahn" <msp...@localnet.com> wrote:
It is quite well known to most people who have ever dealt with 3d vector
algebra, but it is true that it has no particular name, probably because
it is only one result among many others in 3d vector algebra.
Ken Pledger
"Mark Spahn" <msp...@localnet.com> wrote:
> ....
> I'm still blown away by the fact that this formula for the
> computing area of a triangle from its vertex coordinates
> is not well known, and I wonder whether this obscurity is
> due to the fact that -- unlike Heron's Rule for a similar
> formula for computing the area of a triangle from the lengths
> of its sides -- it doesn't have a name.
> Maybe it will become better known if we give it a name like
> "Decartes's Rule"....
and risk replacing one mistake by two?
"Heron's Rule" is probably due to Archimedes. Heron wrote a handy
collection of formulae from various sources, not at all pretending that
they were due to himself. Nevertheless, more recent people who found
the triangle area formula in Heron's list casually named it after him,
instead of paying attention to the Arab mathematician al-Biruni who
ascribed it to Archimedes.
Ken Pledger.