Suppose we're given 3 random points $p_0=(x_0,y_0),p_1=(x_1,y_1),p_2=(x_2,y_2)$ from a two-dimensional continuous uniform distribution $\{U(a,b)\}^2$, for some $(a\in\mathbb{R})\lt (b\in\mathbb{R})$, and it is known that $y_0\lt y_1\lt y_2$.

Also, let $B(x):\mathbb{R}\rightarrow\mathbb{R}$ be the function which graphs the perpendicular bisector of $p_0$ and $p_1$, such that $(x,B(x))$ intercepts the perpendicular bisector.

Finally, let $p_b=(x_2,B(x_2))$, let $d_1=dist(p_1,p_b)$, and let $d_2=dist(p_2,p_b)$, where $dist(\alpha,\beta):\mathbb{R^2,R^2}\rightarrow\mathbb{R}$ is the Euclidean distance between the points $\alpha$ and $\beta$.

  1. Assuming $x_2\lt x_1$, what is the probability that $d_2\lt d_1$?
  2. Assuming $x_2\gt x_1$, what is the probability that $d_2\gt d_1$?

As a side note, in case anyone can point me to a source which may have information related to what I'm looking for, these questions are part of my attempting to do some analysis and optimization of Fortune's algorithm, which used to generate Voronoi diagrams, given a set of points.

  • 1
    $\begingroup$ Got something for you: the region in which $d_2 > d_1$ is the area contained outside the lobes of a right hyperbola with asymptotes that pass through the midpoint of $p_1p_2$ and bisect the angle that $p_1p_2$ make with vertical lines. $\endgroup$ – Dan Uznanski Sep 20 '15 at 22:50
  • $\begingroup$ @DanUznanski This implies that the region in which $d_2\lt d_1$ is the area contained inside the lobes of the same hyperbola. And since it is given that $y_0\lt y_1\lt y_2$, $p_2$ therefore cannot be in the bottom lobe. $\endgroup$ – Steven Fontaine Sep 21 '15 at 3:07

First, let's find the perpendicular bisector of the line $p_0p_1$.

We'll call the midpoint of $p_0p_1$ $M$, and its slope $s$. Also, $s'$ will be the slope of the bisector, $s' = -1/s$.

$$y = s'(x - M_x) + M_y = -\frac{x - M_x}{s} + M_y$$

Now, let's find the location of a $p_2$ that happens to be exactly the same distance from $p_b$ as $p_1$ is (it'll also be the same distance as $p_0$, since $p_b$ is on the bisector).

$$y_2 = y_b - \sqrt{(y_b - y_1)^2+(x_b-x_1)^2}$$

But $y_b$ is on the line, so we can find its location based on $x_b$, and actually $x_b = x_2$, so

$$y_2 = s'(x_2-M_x)+M_y - \sqrt{(s'(x_2-M_x)+M_y - y_1)^2+(x_2-x_1)^2}$$

Everything below this has $d_2 > d_1$.

From here you'll have to integrate to find the probabilities you need. I'm not entirely sure if that is nicely integrable though.

  • $\begingroup$ Also, this is complicated by the fact that $p_2$ must be inside $[a,b]^2$, yet the function for $y_2$ can possibly extend beyond $[a,b]^2$, as seen here: imgur.com/u3qsUvt $\endgroup$ – Steven Fontaine Sep 21 '15 at 13:23

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.