[Guest]

Consider a circle of any size. Then randomly mark 4 points on it. What is the probability of the quadrangle that is formed by these 4 points, to be a "regular quadrangle". Excuse me for this term, as I don't know how to word it. I mean this: A quadrangle that each interior angles of it is smaller than 180⁰ , or with another word: each exterior angles of it is greater than 180⁰

[Prime]

The average length of the sides of the 3 million triangles of the previous post [random vertices] was .664....

That is just slightly less than 1/3 of the diameter, not of the average chord length.

If that helps our thinking.

But the average length of a triangle side is not the same thing as average distance between 2 points inside a circle. Being a side of triangle makes additional constraints on the segment length. The solution path was: once the average segment length is found, find the distance to that segment from another random point, and not the other two sides of the triangle. So what would your simulator yield for the average distance between 2 points inside a unit circle? I think PVPA's solution to that may be correct.

Of course, in view of your correction on where the forth point may be, finding the average triangle area is not a solution to the OP, as we thought. The solution seems even more complex now.

But here is one observation: if we take any triangle on an infinite surface (not bounded by a circle), then the probability for the 4th pont to fall in the area where it would make a convex quadrangle is 1/2. (The sectors projected outside the triangle add up to 180^o.) So for a very small triangle in the center of the circle, the probability tends to 1/2.

[bonanova]

But the average length of a triangle side is not the same thing as average distance between 2 points inside a circle.

Being a side of triangle makes additional constraints on the segment length.

The solution path was: once the average segment length is found, find the distance to that segment from another random point, and not the other two sides of the triangle.

So what would your simulator yield for the average distance between 2 points inside a unit circle?

I think PVPA's solution to that may be correct.

Of course, in view of your correction on where the forth point may be, finding the average triangle area is not a solution to the OP, as we thought. The solution seems even more complex now.

But here is one observation: if we take any triangle on an infinite surface (not bounded by a circle), then the probability for the 4th pont to fall in the area where it would make a convex quadrangle is 1/2. (The sectors projected outside the triangle add up to 180^o.) So for a very small triangle in the center of the circle, the probability tends to 1/2.

Sure it is. All the points are randomly chosen.

I ran a program that just chose two points and verified this.

Agree with unbounded result of 1/2.

[bonanova]

Referring to my drawing 2 or 3 posts back,

p(convex) = 1 - <T> - <T₁+S₁> - <T₂+S₂> - <T₃+S₃>.

I previously noted that I found <T> = 0.2321 +/- .0002 = 7.388% of the disk.

I went back and evaluated <T₁+S₁>, <T₂+S₂> and <T₃+S₃>.

They are all the same [as expected], but also they are equal to <T>! [not expected].

Thus p(convex) = 1 - 4<T> = 1 - 4 x .07388 = 0.70448

So all we need for a solution is a closed form for <T>. Well, also a proof that <T> = <T_i+S_i> i=1-3.

Consider PVPA_Math's suggestion using <distance> = 2/3 [1/3 of the diameter]

He gets 1/2 <distance>² = 1/2 [2/3]² = .222 = 7.072% of the disk.

That is quite accurate.

[unreality]

about the problem of a line with length x, and finding the average distance between two random points on the line, couldn't you do it

Make line of length x into a square, defined by two equal lines, both of length x, at right angles. Oh and by line I mean line segment

Place both points on each line.

Now think of the two lines as two radii of a circle of radius x. Draw the arc connecting the closer two points and the arc connecting the farther two points.

From there, there are some arc-radius formulas that are coming blankly to my mind now But I'm pretty sure I was going somewhere with this

Another method would be looking at the "perfect condition". For example, if you had one point, the perfect condition is right in the center, dividing the line into halves. Two points divide into thirds, three points into quarters, etc.

With two points, the perfect condition is equally spacing them to create three perfect thirds of the line. Thus the distance between the points is 1/3 of the overall length.

I'm willing to bet that, if you took 3 points on a line and averaged the distance between the FARTHEST APART two points, the average would be 1/2. The availability of a middle point might change it, but if the "perfect condition" theory holds true, then it shouldn't

Edited December 19, 2008 by unreality

[bonanova]

I'm willing to bet that, if you took 3 points on a line and averaged the distance between the FARTHEST APART two points, the average would be 1/2.

Yup.

Any number N of randomly chosen points will tend to divide the interval into N+1 equal partitions.

What - they don't all tend to fall at the middle?

Individually, yes.

Interesting.

[bonanova]

I computed distance incorrectly in two previous posts.

Average distance is not .664, which I took to be 1/3 the diameter.

I simulate the average distance on the unit-radius disk as .9047 +/- .0027

Random triangle area is still correct: .232 +/- .002

And convex probability is still .7044 +/- .0004

I found several references for average distance. Here's one.

For the unit disk it gives 64[diameter]/45pi = 128/45pi = .905414, agreeing with the simulation.

[Prime]

It is time to do what Bonanova calls a “sanity check”.

We are in agreement here that the average distance between two points on a segment is 1/3 length of that segment.

Two non-coinciding points inside a disk lie on a chord of that disk. The longest possible chord is a diameter. It stands the reason that the average distance between two random points on a diameter of a circle would be on average 1/3 of the length of the diameter apart, like with any other segment.

But, the diameter is the longest segment on which two points inside a circle may be found. There are lots and lots of other shorter chords inside a circle. 1/3 lengths of the shorter chords would drag the overall average down. So, in a circle of the radius 1, we should expect overall average noticeably below 2/3.

Here is my solution for the average distance between 2 points inside a circle.

Let’s go over the simple formula for the average first. Suppose, we have i segments of length L1, j of L2, and k of L3. Then we would calculate average length as following: Lavg = (i*L1+j*L2+k*L3)/(i+j+k).

Let’s take a point P1 anywhere on a sheet of paper. If P1 is inside a unit circle, where the center of such a circle can be? If we draw a unit circle with the center at P1, the entire area inside that circle represents possible placements for the center of another unit circle capturing P1.

Let’s do the same for another random P2. The intersection of the two circles around P1 and P2 is the area where we could place a center of a circle of radius 1 so that both P1 and P2 are inside that circle.

My theory is that the area of the intersection of the two unit circles P1 and P2 is representative of the number of placements of a segment P1-P2 inside a unit circle. The area of intersection varies from a full circle area Pi*R² = Pi (for R=1) when P1 and P2 coincide, to zero when P1 and P2 are 2R=2 units apart.

Let x be the distance between P1 and P2, A -- the area of the intersection. Then we would calculate the average distance as

Sum[x=0 to 2](x*A)/Sum[x=0 to 2](A). When x goes monotonously from 0 to 2 such sums are represented by integrals.

The intersection area consists of two equal circular segments whose chords are x/2 from the center. The area for such intersection is

2R²cos^-1(x/2) - x(R² - x²/4)^1/2.

Substituting R with 1, we get:

2cos^-1(x/2) - x(1 - x²/4)^1/2.

The integral for the above exp​ression (using Wolfram’s online integrator):

1/6(4-x²)^3/2 – 2(4 - x²)^1/2 + 2xcos^-1(x/2).

Plugging in the boundaries (x from 0 to 2), the definite integral yields 8/3.

That number is a proportionate representative of the number of all segements.

Now we calculate the integral of segment length times its corresponding intersection area. That would be the exp​ression: 2xcos^-1(x/2) - x²(1 - x²/4)^1/2,

The integral of which is

1/8(cos^^-1(x/2)x² - (4 - x²)^1/2(x² +2)x + 8sin^-1(x/2))

Plugging in the boundaries (x from 0 to 2), the above exp​ression evaluates to Pi/2.

Now, for the final answer the average segment length is (Pi/2)/(8/3) = 3Pi/16 ~ 0.589.

That is larger than I expected.

Note, the intersection of unit circles could be used as a representative of probability for placement 3 and 4 points inside a unit circle. We could use it for solving the OP.

[bonanova]

That result seems to be less than 1/3 the diameter.

In two dimensions you have more freedom, so shouldn't it be greater than 1/3?

P₂ {r₂,theta}, P₁ {r₁,0}

Distance = sqrt[r₁² + r₂² - 2r₁r₂ cos(theta)]

sqrt(radius) density gives uniform areal density.

<Distance> = {I₀^2pi I₀¹ I₀¹ [r₁ + r₂ + sqrt(r₁r₂)cos(theta)] dr₁ dr₂ dtheta}/pi

[Prime]

That result seems to be less than 1/3 the diameter.

In two dimensions you have more freedom, so shouldn't it be greater than 1/3?

P₂ {r₂,theta}, P₁ {r₁,0}

Distance = sqrt[r₁² + r₂² - 2r₁r₂ cos(theta)]

sqrt(radius) density gives uniform areal density.

<Distance> = {I₀^2pi I₀¹ I₀¹ [r₁ + r₂ + sqrt(r₁r₂)cos(theta)] dr₁ dr₂ dtheta}/pi

I ran my own simulation of random placement of 2 points inside a unit circle (of radius 1) and came up with the result of approximately 0.725.

The simulation was done in Excel. Each point inside a unit circle is represented by a pair of numbers:

1) r -- the distance from the center of the coordinates. 0 <= r < 1.

2) a -- the angle between segment r and the X axis. 0 <= a < 2Pi.

The distance between two points is calculated, as Bonanova pointed out,

D = (r₁² + r₂² - 2r₁r₂cos(a₁ - a₂))^1/2, where (a₁ - a₂) is the angle between the two vectors.

Dim avg As Double, r1 As Double, r2 As Double, a1 As Double, a2 As Double
Dim d As Double, n As Long, Pi As Double
Randomize
avg = 0
Pi = Application.WorksheetFunction.Pi()
For n = 1 To 100000
r1 = Rnd
a1 = Rnd * 2 * Pi
r2 = Rnd
a2 = Rnd * 2 * Pi
d = Sqr(r1 ^ 2 + r2 ^ 2 - 2 * r1 * r2 * Cos(a1 - a2))
avg = avg + (d - avg) / n
Next n
ActiveCell.Value = avg
End Sub

Sub circ2pts()

I was under the impression that all possible point pairings could be tied to chords inside the circle. Thus, the average distance would be less than 1/3 of the diameter. But, I have to give up that theory. Indeed, two dimensions seem to offer more freedom.

Random point picks for calculating the average, is an approximation. The actual average is the value obtained from the collection of all possible point pairings.

A disk can be viewed as a collection of chords packed infinitely close to each other (FIG.1). I based solutions for the average point distance on just one instance of such parallel chord collection. I reasoned that if I turn the disk a notch, I would end up with a logically identical collection of chords, which would have the same average point distance and by turning the disk, I could get every possible point pair (including orientation in 2-D space.) (FIG. 2).

However, when you turn the disk, the resulting space to be accounted for is not distributed evenly (FIG. 3). And so, a correct solution must take into account the rotation, or orientation of the pair of points in a 2-D space.

I’m at loss how to evaluate the triple integral suggested by Bonanova. However, I have a new solution in mind. If it works out, I’ll post it here.

[Prime]

...

I found several references for average distance. Here's one.

For the unit disk it gives 64[diameter]/45pi = 128/45pi = .905414, agreeing with the simulation.

In one of my attempts to solve the problem analytically I came up with the same result. But I discarded it as it seems to count in some point pairings falling outside the circle. Besides, it does not agree with my simulation of 0.725.

[bonanova]

In one of my attempts to solve the problem analytically I came up with the same result.

But I discarded it as it seems to count in some point pairings falling outside the circle.

Besides, it does not agree with my simulation of 0.725.

whether in your simulation you took angles at random from 0 to 2pi and radial values at random from 0 to 1.

That could account for your smaller average length: crowding your sample points near the origin.

[To see this, sketch circles at radii .1 .2 .3 .4 ... .9 1, with points at equal angular increments.]

[bonanova]

Referring to my drawing,

At first I was surprised when I found that the four red areas had equal average value.

After some thought it's obvious that their averages must be equal.

Recall that the triangle T has points P1 P2 and P3 as vertices.

Convexity fails should the 4th point P4 fall in T's interior.

That is the configuration of failed convexity: one point falls inside the triangle of the other three.

Consider then why the red regions are equivalent:

1. T is the region of P4 that makes P4 fall inside triangle P1 P2 P3
   
2. T1+S1 is the region of P4 that makes P1 fall inside triangle P2 P3 P4.
   
3. T2+S2 is the region of P4 that makes P2 fall inside triangle P1 P3 P4.
   
4. T3+S3 is the region of P4 that makes P3 fall inside triangle P1 P2 P4.
   

Thus the red regions all depict the same thing.

They are the loci of 4th points, given P1 P2 P3, that result in a shell of three random points enclosing a 4th random point.

Thus they must all have the same average area.

Rephrasing:

If we lay down P1 P2 P3 and ask where P4 produces convexity failure, it's the union of the four red areas.

If we lay down P1 P2 P3 and ask where P4 will be the interior point, that's just T.

Since the interior point can with equal probability be any of the points, we can simply multiply any particular case by four.

Thus the sum of the four areas must be 4<T>.

Since by symmetry the other three are equal, all 4 are equal.

We may simply write:

p(convex) = 1 - 4<T>/pi = 1 - 4 x .2321.../pi = 1 - .2955... = .7044...

[bonanova]

with vertices P₁(x₁, y₁), P₂(x₂, y₂), P₃(x₃, y₃) is given by

.........| x₁ y₁ 1 |

A = .5 x | x₂ y₂ 1 |

.........| x₃ y₃ 1 |

The average area <A> of a triangle on a unit disk is then

......I₃ I₂ I₁ |A| dx₁ dy₁ dx₂ dy₂ dx₃ dy₃

<A> = ----------------------------------

......I₃ I₂ I₁ ... dx₁ dy₁ dx₂ dy₂ dx₃ dy₃

where I_i represent integrals over the region x_i²+y_i² <= 1.

It's not a pretty sight, but it's been done, and the result is 35/48pi = 0.2321009587...., in agreement with simulation.