7
$\begingroup$

You are given 3 points in $\mathbb{R}^2$; $A$, $B$, $C$ forming a triangle with area > 0. You pick an arbitrary point inside $ABC$ and an arbitrary direction. After some distance $d$, you will intersect some side of a triangle. The task is to compute the expected $d$ for a given triangle. Also, it would be nice to know the whole distribution. What kind of distribution (e.g. uniform, normal) would it be?

Next, what if I have a complex polygon? Can I combine my knowledge from individual triangles somehow to compute mean and distribution for the convex polygon?

Finally, how about a non-convex polygon?

$\endgroup$
8
$\begingroup$

If you call the random variable you described X, then it's much easier to compute the expected value of X2. Indeed, for any point P inside triangle ABC, the expected value of X2 where X is the length of a ray through P intersected with the interior of ABC is just the area of ABC divided by π—imagine trying to compute the area of ABC using polar coordinates with origin at P.

You can use a similar trick to write the expected value of X in terms of the average value of 1/d(P, Q) where P and Q are selected uniformly at random from the interior of triangle ABC, but this doesn't seem terribly helpful.

$\endgroup$
2
$\begingroup$

We can start by solving the problem for an arbitrary triangle and a fixed direction, say the upward direction, as we can always rotate the whole figure into that position.

In the generic case, no edge of the triangle is horizontal. Thus the triangle has a "top" vertex at $(0, 0)$ -- this is the vertex with the largest y-coordinate. Without loss of generality, rescale so that the edge opposite the vertex at $(0, 0)$ passes through $(-1, 0)$. We'll say that the "height" of this triangle is 1, where by height we mean the length of the vertical dropped from the top vertex.

Then the set of points of vertical distance at least $r$ from the top of the original triangle form a triangle of height $1-r$, similar to the original triangle. Thus

$$ Prob(\hbox{vertical distance from top } > r) = (1-r)^2 $$

and this gives the distribution. In particular the expected value of the vertical distance from a random point to the top of the triangle (after the rescaling given above) is $1/3$.

If you want to pick a random direction, though, then this gets a lot harder because the rescaling step will act differently for different directions.

$\endgroup$
  • $\begingroup$ Trying to draw this. What is r? $\endgroup$ – S. Donovan Jan 2 '10 at 5:30
1
$\begingroup$

For a triangle, this seems relatively easy. construct the voronoi diagram of the sides, which in this case is merely the partition formed by the angle bisectors at each vertex. they intersect at the center of the incircle, forming three triangles. In each triangle, the 'distance to boundary' is really the distance to the corresponding side of the original triangle, and the answer is a straight integration.

$\endgroup$
  • 3
    $\begingroup$ I think the ray is in a uniformly random direction, not towards the nearest point on the boundary. $\endgroup$ – Reid Barton Jan 2 '10 at 5:04
  • 2
    $\begingroup$ ah dang. good point. missed that $\endgroup$ – Suresh Venkat Jan 2 '10 at 5:08
1
$\begingroup$

x is in the triangle. Draw segments that connect x to each vertex and segments perpendicular to each side from x. Then, starting from the nearest perpendicular segment, measure the angle formed by your vector and call it $\theta$. Note the length of the perpendicular, call it R. Then the distance, from x to the side in the direction of the vector, is: $R \sec (\theta)$.

$\endgroup$
  • $\begingroup$ This works for the convex... but not for the non-convex. $\endgroup$ – S. Donovan Jan 2 '10 at 5:03
1
$\begingroup$

I know this question was asked more than eight years ago. Still, here's the answer for the triangle and the rectangle case. I'm sure they can be extended to other convex polygons too..

An Expected Value problem III

EDIT: Yes, that's my blog. The answer is easy to obtain but a bit long to explain. Unfortunately, I'm not sure when I'll be posting it. If that's not the norm in SO, I request the moderators to delete this answer. I'll post it again when I've completed my answer in my blog. Thanks.

EDIT: I've updated the proof in the blog.

$\endgroup$
  • 2
    $\begingroup$ (1) Is that just a formula with no proof or hint as to how they got it? (2) Is that your blog? If so, you should probably specify that in your answer. $\endgroup$ – Federico Poloni Sep 21 '17 at 17:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.