This is a HW question for the course MAT480 (Mathematical Modelling I) at Athabasca University. I'm taking this distance course for credit in order to graduate sooner. Having a hard time putting all pieces together.
Question
A business park occupies a square area with sides of length 2M. Two copy shops are located symmetrically on the north-south line that bisects this square, at positions (0, +d) and (0, -d) in Cartesian co-ordinates, with the origin at the centre of the square.
Assume that a third copy shop plans to locate at a position (r,0)
Taking d = pM and r = qM with $0\le p , q\le 1$, use a Voronoi analysis to compute the area of the territory whose points are closest to this new shop. You will need to consider three separate cases.
a. Show that these three cases are distinguished by the conditions:
- Case 1: $0\le p \le q \le 1$
- Case 2: $0 \le \sqrt{1+p^2} - 1\le q \le p \le 1$
- Case 3: $0 \le q \le \sqrt{1+p^2} -1 \le p \le 1$
What I have figured out
I spent about countless hours figuring out what I have so far, and 1 hour with one very kind teacher at University of Ottawa too. Here:
- Scale: instead of dealing with the original square of area $4M^2$, I simply use a square of area of 4 $units^2$ (i.e. first quadrant is unit square.)
- The above makes us deal with points at $(0, \pm p)$ and $(q, 0)$.
- First Quadrant: I'm only looking at the first quadrant (perhaps second when needed) to compute area. Then multiply by two, everything is symmetrical below.
- Points: new shop $(q, 0)$ is P, two old shops are S1 $(0, p)$ and S2 $(0, -p)$
Let $l$ be the line of the Voronoi diagram that "cuts" through first quadrant diagonally. This line is all the middle points between S1 and P and, as a function of $x$ is simply:
$$ l = \frac{p^2 - q^2}{2p} + x \frac{q}{p} $$
- Let Q be the point where the Voronoi vertices meet. It's the point at same distance of P, S1 and S2. We note that Q lays on the x-axis (it's the intersect of $l$) and has coordinates $(x_Q,0)$ Thus:
$$ x_Q = \frac{q^2 - p^2}{2q} $$
- Let W be the point where $l$ intersects with the line $y=1$. W has coordinates $(x_W, 1)$ Thus:
$$ x_W = \frac{p}{q} + x_Q = \frac{p}{q} \left( 1 + \frac{q^2 - p^2}{2p} \right) $$
- Let Z be the point where $l$ intersects with the line $x=1$. Z has coordinates $(1, y_Z)$ Thus:
$$
y_Z = \frac{q}{p} + \frac{p^2 - q^2}{2p}
$$
Case 1
Now, as you can probably envision, the difference between the three cases is really a matter of "how" the area is computed. What I can completely understand, right of the start is that Case 1: $0\le p \le q \le 1$ is that only time when the origin DOES NOT belong to P territory.
We noticed that here, $x_Q \ge 0$ (obvious since $q \ge p$) and that $x_W \leq 1$. Here's why:
$$ x_W \le 1 $$ $$ \frac{p}{q} + x_Q \le 1 $$ $$ \frac{p}{q} \le 1 - x_Q $$ $$ p \le q - qx_Q $$ $$ p \le q $$
So the area is simply "area triangle" + "area rectangle" times 2:
the area of the rectangle triangle of height 1 running from $x_Q$ to $x_W$
PLUS
the area of the rectangle of height 1 running from $x_W$ to 1.
(mult by 2).
I got:
$$ 2 \left[ \frac{(x_W - x_Q)(1)}{2} + (1-x_W)(1) \right] = x_W - x_Q + 2 - 2x_W = 2 - x_Q - x_W = 2 - x_Q - \left(\frac{p}{q} + x_Q\right) = 2 - 2x_Q - \frac{p}{q} = 2 + \frac{p^2 - p - q^2}{q} $$
Case 2 and Case 3
Of course, here, $x_Q \leq 0$ so the origin is now part of P territory.
This is where my work has come to an abrupt halt. I'm still having trouble making sense of the condition including $\sqrt{1+p^2}$. I know what it is geometrically, it's the length of the hypothenuse of the triangle S1, origin and $(1,1)$, or more simply, it's the distance from S1 to $(1,1)$.
My intuition tells that that wether $q$ is bigger or smaller than $\sqrt{1+p^2} -1$ will make $x_W$ be before/after the line $x=1$ ... but how?
I've tried several inequalities to no avail.
Where I need your help, simply:
For now, I think it boils down to this...
Is $x_W$ smaller or greater than 1 in cases 2 and 3? Recall the info above:
- Case 2: $0 \le \sqrt{1+p^2} - 1\le q \le p \le 1$
- Case 3: $0 \le q \le \sqrt{1+p^2} -1 \le p \le 1$
$$ x_W = \frac{p}{q} \left( 1 + \frac{q^2 - p^2}{2p} \right) $$
Thanks for your help!
I think you would do well to think first about the shape of the Voronoi region belonging to $(qM,0)$ as $q$ ranges from $0$ to $1$. Actually it's convenient to describe the shape of the "top half" of this region, i.e., the half above the $x$ axis. That region starts as a trapezoid with two parallel vertical lines for small $q$ (indeed, it's a rectangle when $q=0$), becomes a right triangle at some positive value of $q$, and then becomes a trapezoid again, this time with two parallel horizontal lines (i.e., the $x$ axis and the line at $y=M$) when $q$ gets close to $1$. The second transition occurs when the corner point $(M,M)$ of the square is equidistant from $(qM,0)$ and $(0,pM)$, and this clearly occurs when $q=p$; the first transition occurs when the midpoint $(-M,0)$ of the left side is equidistant from $(qM,0)$ and $(0,pM)$, and this occurs when $(q+1)^2 = 1+p^2$.
It really helps to draw the pictures.