Parabola equation in Fortune algorithm for building Voronoi diagram

Question

in DeBerg's "Algorithms and Applications", the part about Voronoi diagram, i have encountered the following formula for parabola arising in the beach line for a site point:

$$\beta := y = \frac{1}{2(p_{j,y}-l_y)}(x^2-2p_{j,x}+p_{j,x}^2 + p_{j,y}^2-l_y^2),$$ where $(p_{j,x}, p_{j,y})$ is the site point and $l_y$ is sweep line $y$ coordinate.

Why $\frac{1}{2(p_{j,y}-l_y)}$ multiplies $(x - p_{j,x})^2?$

I think equation of the parabola must be

$$y = (x - p_{j,x})^2 + (p_{j,y}+l_y)/2.$$

EDIT: Thanks to Erick Wong, who pointed out that equation from the book is scale-invariant. But i don't understand, why they would need scale-invariance? And why this divisor?

Answer 1

Too see why we need this multiplier $\frac{1}{2(p_{j,y}-l_y)}$ for $(x - p_{j,x})^2$ we must notice what shape of parabola changes with sweep line movement.

At the very beginning, when new site is just hit the line it is effectively just a vertical line and while sweep line moves downward it became wider and wider.

Answer 2

I somehow stumbled across this equation trying to find it myself. The equation actually can be found by using the vertex form equation of a quadratic graph;

y = a(x - h)² +k

It should be understood that the vertex of the parabola is equal to the midpoint of the line representing the shortest distance between the generator and the sweep line. Hence, the vertex

(h, k) = (p_{j, x}, ^{(p_{j, y} + l_y)}⁄₂)

Thus, giving you y = a(x - p_{j, x})² + ^{(p_{j, y} + l_y)}⁄₂

This seems to be where you got to. a, however, needs to be accounted for as it defines the concavity and scale of the graph. To determine a, another point on the graph is required. For this, take the point on the parabola horizontally on the right of the generator referring to the figure below.

Point n on parabola

The distance between p_j and n is equal to the distance between p_j and the sweep line. Thus, the coordinate of

n = (p_{j, x} + p_{j, y} - l_y, p_{j, y})

By substituting this point into the quadratic formula, a can be found

p_{j, y} = a(p_{j, x} + p_{j, y} - l_y - p_{j, x})² + ^{(p_{j, y} + l_y)}⁄₂

a(p_{j, x} + p_{j, y} - l_y - p_{j, x})² = p_{j, y} - ^{(p_{j, y} + l_y)}⁄₂

a(p_{j, y} - l_y)² = ^{(p_{j, y} - l_y)}⁄₂

a = ^{(p_{j, y} - l_y)}⁄_{(2(pj, y - ly)²)}

a = ¹⁄_{(2(pj, y - ly))}

Therefore, the overall equation would be y = ¹⁄_{(2(pj, y - ly))}(x - p_{j, x})² + ^{(p_{j, y} + l_y)}⁄₂, and would be why ¹⁄_{(2(pj, y - ly))} multiplies (x - p_{j, x})².

This may not be the cleanest method but this is the method I used to derive the same formula you posted. Hope this helps.