Math Is Fun Forum

Macka

Member

Registered: 2006-10-30

Posts: 8

Voronoi Edge Equation [Rather Urgent]

Does anyone know how to "Determine the equation of the Voronoi edge for points A and B" ?

I have 3 points (A,B,C) and yes it is a poorly drawn ascii diagram

                                    A
                                      ^
                                   /60°\
                                 /         \
                               /             \
                             /45°       75°\
                           <____________>  B

as i said above, i need to determine the equation for the Voroni edges, initially i found the equation for the lines connecting A,B,C but i just realised what the question is asking and my assignment is due in 10 hours, oh and its currently 11pm so you may have figured im freaking out.

All help appreciated

gnitsuk

Member

Registered: 2006-02-09

Posts: 121

Re: Voronoi Edge Equation [Rather Urgent]

When you say Voronoi edge of say AB, do you mean the perpendicular bisector of AB? And you know the corrdinates of A,B and C in the plane?

Macka

Member

Registered: 2006-10-30

Posts: 8

Re: Voronoi Edge Equation [Rather Urgent]

When you say Voronoi edge of say AB, do you mean the perpendicular bisector of AB? And you know the corrdinates of A,B and C in the plane?

well, i assume thats what it means, yes, im pretty sure thats it...
and yes, i know the the coords
A (10,11)
B (11,4)
C (2,5)

gnitsuk

Member

Registered: 2006-02-09

Posts: 121

Re: Voronoi Edge Equation [Rather Urgent]

Ok, cool.

So the problem reduces to finding the equation of the perpendicular bisector of two points.

I'll do it with a numerical example.

Say the two points are A(1,3) and B(2,9).

We use this simple fact:

The product of the gradients of perpendicular lines is -1.

So, the gradient ot the line through AB is (9-3)/(2-1) = 6

So the gradient of a line perpendicular to AB is -(1/6) because 6 * -(1/6) = -1

Cool, so you know the gradient of the perpendicular bisector - call it m.

Now you need the intercept of the bisector - call it c. Well, we know the bisector contains the midpoint of AB which in this case is ((1 + 2) / 2,(3 + 9)/2) = (3/2,6) so to find the intercept we use y = mx + c with say x = 1 and y = 3 and m = -(1/6) which gives c = 19/6 so the equation of the perpendicular bisector is y = -(1/6)x + 19/6.

I'm sure you'll be fine now. Let me know.

Macka

Member

Registered: 2006-10-30

Posts: 8

Re: Voronoi Edge Equation [Rather Urgent]

Ok, I understand
the equation of a straight line part
the gradient part (Rise/Run)
how did you get the product of the gradients of perpendicular lines?

gnitsuk

Member

Registered: 2006-02-09

Posts: 121

Re: Voronoi Edge Equation [Rather Urgent]

Here's one way:

http://library.thinkquest.org/C0110248/geometry/analyperp.htm

Macka

Member

Registered: 2006-10-30

Posts: 8

Re: Voronoi Edge Equation [Rather Urgent]

Correct me if im wrong...
the product of the gradient for a line multiplied by the gradient of the line's perpendicular bisector always = -1
so the if the gradient for AB = -3 then the product of -3 and the gradient of the line perpendicular to AB is -1 therefore  m*-3=-1  ..... m=(-1)/(-3) ..... m=1/3 so the gradient of the line perpendicular to AB = 1/3

Correct?

Last edited by Macka (2006-10-30 01:51:20)

gnitsuk

Member

Registered: 2006-02-09

Posts: 121

Re: Voronoi Edge Equation [Rather Urgent]

Yes. That's right.

Macka

Member

Registered: 2006-10-30

Posts: 8

Re: Voronoi Edge Equation [Rather Urgent]

Just thought i would update you guys, i finished the assignment in time, even though i litterally re did the whole thing 4 or 5 times..
and i got 37/40 !!

Thankyou to gnitsuk!