Question

1. a town is in the form of a square of 4 kilometers. the square is described by the coordinate system ( 0 leq x leq 4, 0 leq y leq 4 ). the town has four fire stations located at points ( (1, 1) ), ( (3, 1) ), ( (1, 3) ), and ( (3, 3) ). each station services the part of town that is nearer to their station than any other station. sketch a voronoi diagram to represent this information.

1. the town decides to build another fire station at point ( (2, 2) ). the parts of town serviced by the stations are redistributed. sketch a new voronoi diagram to represent this new situation.

Explanation:

Step1: Plot fire stations (Q1)

Mark points $(1,1)$, $(3,1)$, $(1,3)$, $(3,3)$ on $0 \leq x \leq 4, 0 \leq y \leq 4$ grid.

Step2: Find bisectors (Q1)

• Perpendicular bisector of $(1,1)$ & $(3,1)$: $x=2$
• Perpendicular bisector of $(1,1)$ & $(1,3)$: $y=2$
• Perpendicular bisector of $(3,1)$ & $(3,3)$: $y=2$
• Perpendicular bisector of $(1,3)$ & $(3,3)$: $x=2$

Step3: Sketch Q1 Voronoi diagram

The lines $x=2$ and $y=2$ divide the square into 4 smaller squares:

1. Region for $(1,1)$: $0 \leq x < 2, 0 \leq y < 2$
2. Region for $(3,1)$: $2 < x \leq 4, 0 \leq y < 2$
3. Region for $(1,3)$: $0 \leq x < 2, 2 < y \leq 4$
4. Region for $(3,3)$: $2 < x \leq 4, 2 < y \leq 4$

The lines $x=2$ and $y=2$ are the edges between regions.

Step4: Plot new station (Q2)

Add point $(2,2)$ to the grid with the original four stations.

Step5: Find new bisectors (Q2)

• Bisector of $(1,1)$ & $(2,2)$: $y = x$
• Bisector of $(3,1)$ & $(2,2)$: $y = -x + 4$
• Bisector of $(1,3)$ & $(2,2)$: $y = -x + 4$
• Bisector of $(3,3)$ & $(2,2)$: $y = x$

Step6: Sketch Q2 Voronoi diagram

The lines $y=x$, $y=-x+4$, $x=2$, $y=2$ divide the square:

1. Region for $(1,1)$: Bounded by $x=0$, $y=0$, $y=x$, $x=2$, $y=2$
2. Region for $(3,1)$: Bounded by $x=4$, $y=0$, $y=-x+4$, $x=2$, $y=2$
3. Region for $(1,3)$: Bounded by $x=0$, $y=4$, $y=-x+4$, $x=2$, $y=2$
4. Region for $(3,3)$: Bounded by $x=4$, $y=4$, $y=x$, $x=2$, $y=2$
5. Region for $(2,2)$: Central square bounded by $y=x$, $y=-x+4$, $x=2$, $y=2$

Answer:

1. Voronoi Diagram for 4 stations:

The square $0 \leq x \leq 4, 0 \leq y \leq 4$ is divided by vertical line $x=2$ and horizontal line $y=2$ into 4 equal 2x2 sub-squares, each containing one fire station at its center, forming the Voronoi regions.

1. Voronoi Diagram for 5 stations:

The square is divided by the lines $y=x$, $y=-x+4$, $x=2$, and $y=2$. The original four outer regions are each a right triangle/quadrant, and a central square region surrounds the new station $(2,2)$.