3
$\begingroup$

Although the MO question Limit of lights in rooms was quickly closed, it suggests a related question:

Q0. What is the probability that a random quadrilateral $Q$ is entirely illuminated from a random point $p \in Q$?

What is a "random quadrilateral"? What constitutes a random simple polygon is not easily answered. See Jeff Erickson's webpage on this topic. But perhaps we can take this as the following definition of a random quadrilateral:

Let $p_i$ be four points uniformaly randomly distributed in a unit-radius disk. Let $Q$ be the quadrilateral formed by connecting the points in order: $(p_1,p_2,p_3,p_4,p_1)$. A certain fraction of these will have crossing segments, and the others will be simple polygons. My simulations suggest that about half are simple, half have segment crossings.

Q1. What percentage of quadrilaterals (as described above) are simple (non-self-crossing)? Near $\tfrac{1}{2}$? Exactly $\tfrac{1}{2}$?

The answer to Q1 is likely known, but I could neither find it nor derive it.

Among the random simple quadrilaterals $Q$,

Q2. For what proportion does a random internal point $x$ insides $Q$ illuminates all of $Q$?


          QuadIllum
          Any point in the kernel (yellow) will illuminate the quad.
I expect the answer to Q2 is well above a half, nearer to (but less than) $1$.

$\endgroup$
  • 2
    $\begingroup$ Suppose one point is inside the convex hull of the other three. Every point in the triangle illuminates precisely one of the three possible quads one can form from the four points, so in this case I would say the probability is 1/3. In the case of the convex hull being a quad, the probability is one conditional on the points chosen in cyclic order, and let's call it zero if the polygon crosses. My guess is 1/3. Gerhard "Unless This Is Another Paradox" Paseman, 2017.11.17. $\endgroup$ – Gerhard Paseman Nov 18 '17 at 2:04
  • $\begingroup$ @GerhardPaseman: "My guess is 1/3." Useful to have a falsifiable conjecture---May emprical calculations support you! :-) $\endgroup$ – Joseph O'Rourke Nov 18 '17 at 2:10
2
$\begingroup$

Q1: assume that degenerate quadruplets do not exist (they have probability 0 of occuring). Observe that for any non-degenerate quadruple of points $P = (p_1, p_2, p_3, p_4)$ we have exactly one of three options:

  1. $P$ is a quadrilateral;
  2. $p_1 p_2$ intersects $p_3 p_4$;
  3. $p_1 p_4$ intersects $p_2 p_3$.

Let $B$ be the event of segments $p_1 p_2$ and $p_3 p_4$ crossing for random points $p_1, p_2, p_3, p_4$, then the probability of $A = \{P$ that form a quadrilateral$\}$ is $1 - 2 \Pr(B)$.

To find $\Pr(B)$, assign the unique intersection point $p$ to each $(p_{11}, p_{12}, p_{21}, p_{22}) \in B$. Introduce an injective change of coordinates among quadruplets $P$ for which $p$ is defined:

  • $(r, \alpha)$ = polar coordinates of $p$;
  • $(l_{ij}, \alpha_{ij})$ = polar coordinates of $p_{ij}$ with respect to center $p$ and reference direction $\alpha$.

Since $p_{11} p_{12}, p_{21} p_{22} \ni p$, we must have $\alpha_i := \alpha_{i1} = \alpha_{i2} + \pi$ for $i = 1, 2$. $\Pr(B)$ can be found by integrating Jacobian $J = (l_{11} + l_{12})(l_{21} + l_{22})r \sin(\alpha_1 - \alpha_2)$ (up to a sign) over the region where all points lie within the circle (we only integrate for $0 \leq \alpha_1 \leq \alpha_2 \leq \pi$, but multiply by $8$ to account for different orders): $\Pr(B) = 8\int_0^1 dr \int_0^{2\pi} d \alpha \int_0^{\pi} d \alpha_1 \int_{\alpha_1}^{\pi} d \alpha_2 \int_0^{\sqrt{1 - r^2 \sin^2 \alpha_1} - r\cos \alpha_1} dl_{11} \int_0^{\sqrt{1 - r^2 \sin^2 \alpha_1} + r\cos \alpha_1} dl_{12} \int_0^{\sqrt{1 - r^2 \sin^2 \alpha_2} - r\cos \alpha_2} dl_{21} \int_0^{\sqrt{1 - r^2 \sin^2 \alpha_2} + r\cos \alpha_2} dl_{22} \cdot (l_{11} + l_{12})(l_{21} + l_{22})r \sin(\alpha_2 - \alpha_1).$

Integrating $J$ within required bounds seems hard (probably no closed answer...), but numerical integration yields $\Pr(B) \approx 0.23482663$, and $\Pr(A) \approx 0.53034674$, which agrees well with my Monte Carlo computations.

Q2: let $C$ be the event "an unordered set of four random points is in convex position". Considering all $4!$ orderings in each case we can conclude that $\Pr(A) = \frac{1}{3}\Pr(C) + \Pr(\overline{C})$, which implies $\Pr(C) = \frac{3}{2}(1 - \Pr(A)) \approx 0.70448$. A convex quardilateral is lit by a random interior point with probability 1.

Consider a non-convex quadrilateral with convex hull $H = p_1 p_2 p_3$. Conditioned on vertices of $H$, the fourth point $p_4$ is uniformly distributed within the triangle $H$, and the side of $H$ to which $p_4$ is connected is equidistributed. Notice that affine transformations don't change uniformity of distribution nor that a particular interior point lights the quadrilateral. It follows that conditional probability "a random interior point lights a random non-convex quardilateral with convex hull $H$" does not depend on $H$. Let us find it for a standard triangle with vertices $(0, 0), (1, 0), (0, 1)$: $$\frac{\int_0^1 dx \int_0^{1 - x} dy \frac{1 - y(\frac{x}{1 - x} + \frac{1}{x + y})}{1 - y}}{1/2} = 7 - \frac{2\pi^2}{3} \approx 0.420264$$

Hence $$\Pr(\text{a random quadrilateral is lit by a random interior point}) \approx \frac{\frac{1}{3}\Pr(C) + 0.420264\Pr(\overline{C})}{\Pr{A}} \approx 0.676959,$$ which, again, seems to meet the Monte Carlo values pretty well.

$\endgroup$
  • $\begingroup$ Impressive calculations! $\endgroup$ – Joseph O'Rourke Nov 18 '17 at 11:18
  • $\begingroup$ Suppose you replace your standard triangle by an equilateral triangle. Does your integral still produce 0.420 approximately? Gerhard "Things Should Be More Symmetric" Paseman, 2017.11.18. $\endgroup$ – Gerhard Paseman Nov 18 '17 at 11:47
  • $\begingroup$ @GerhardPaseman It has to, because the triangles are interchangeable with an affine map which preserves both area ratios and the illumination condition. You're welcome to try and calculate it for the eq. triangle yourself. Note that the expression under the integral is (the portion that lights the quad) / (the area of the quad), which is the reason why the result is a bit weird. $\endgroup$ – Mikhail Tikhomirov Nov 18 '17 at 11:55
  • $\begingroup$ My geometric intuition (what there is of it) suggests the integral should evaluate to 0.5 for the equilateral triangle. Perhaps I am taking the wrong weights. Gerhard "Needs To Lose Some Weights" Paseman, 2017.11.18. $\endgroup$ – Gerhard Paseman Nov 18 '17 at 11:59

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.