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

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

Step2: Find perpendicular bisectors

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

Step3: Draw first Voronoi diagram

The lines $x=2$ and $y=2$ divide the square into 4 equal smaller squares, each containing one fire station as its Voronoi cell.

Step4: Add new station $(2,2)$

Mark point $(2,2)$ on the second grid.

Step5: Find new bisectors

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

Step6: Draw second Voronoi diagram

The four bisectors intersect at $(2,2)$, dividing the original 4 cells into 8 regions: 4 triangular regions at the square's corners (each around the original stations) and 4 triangular regions adjacent to the center station $(2,2)$.

Answer:

1. The first Voronoi diagram is a square $0 \leq x \leq 4, 0 \leq y \leq 4$ split by the lines $x=2$ and $y=2$ into 4 equal 2x2 smaller squares, with each original fire station at the center of one small square.
2. The second Voronoi diagram has the 5 fire stations marked, with the lines $y=-x+3$, $y=x-1$, $y=x+1$, $y=-x+5$ intersecting at $(2,2)$, creating 8 triangular Voronoi cells (4 corner cells around the original stations, 4 cells adjacent to the center station).