Voronoi diagrams in SciPy - Practice Problems & Coding Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Voronoi vertices coordinates

What is the output of the following code snippet that computes Voronoi vertices for given points?

SciPy

from scipy.spatial import Voronoi
import numpy as np
points = np.array([[0, 0], [1, 0], [0, 1], [1, 1]])
vor = Voronoi(points)
print(np.round(vor.vertices, 2))

A [[0. 0] [1. 0] [0. 1] [1. 1]]

B [[0.5 0.5] [0. 0. ] [1. 0. ] [0. 1. ] [1. 1. ]]

C [[0.5 0.5] [0.5 0. ] [0. 0.5] [1. 0.5] [0.5 1. ]]

D [[0.5 0.5]]

💡 Hint

Voronoi vertices are points equidistant from the input points, often at the center of the input points' convex hull.

The Voronoi diagram for four points at the corners of a square has a single Voronoi vertex at the center (0.5, 0.5). The other options list either input points or incorrect vertices.

❓ data_output

intermediate

Number of Voronoi regions

Given the following points, how many Voronoi regions does the Voronoi diagram have?

SciPy

from scipy.spatial import Voronoi
import numpy as np
points = np.array([[2, 3], [5, 4], [3, 7], [6, 1], [7, 5]])
vor = Voronoi(points)
print(len(vor.regions))

A 7

B 11

C 5

D 10

💡 Hint

The number of Voronoi regions is related to the number of points but includes some empty or infinite regions.

The Voronoi object stores regions for all vertices including empty and infinite ones. For 5 points, the number of regions is 11.

❓ visualization

advanced

Plotting Voronoi diagram with infinite ridges

Which code snippet correctly plots the Voronoi diagram including infinite ridges extended to a finite distance?

SciPy

from scipy.spatial import Voronoi, voronoi_plot_2d
import matplotlib.pyplot as plt
import numpy as np
points = np.array([[1, 1], [2, 3], [3, 1], [4, 4]])
vor = Voronoi(points)
fig, ax = plt.subplots()
# Fill in the missing code to plot infinite ridges

A

voronoi_plot_2d(vor, ax=ax, show_vertices=False, line_colors='orange')
plt.show()

B

voronoi_plot_2d(vor, ax=ax, show_vertices=True)
plt.show()

C

voronoi_plot_2d(vor, ax=ax, show_vertices=False)
plt.xlim(0,5)
plt.ylim(0,5)
plt.show()

D

voronoi_plot_2d(vor, ax=ax, show_vertices=False)
plt.xlim(0,5)
plt.ylim(0,5)
plt.show()  # Infinite ridges are not extended

💡 Hint

Use the parameter to hide vertices and change line colors to highlight edges.

Option A uses show_vertices=False to hide vertices and changes line colors to orange, which helps visualize infinite ridges clearly. Other options either show vertices or do not highlight infinite ridges.

🔧 Debug

advanced

Identify the error in Voronoi region plotting code

What error does the following code produce when trying to plot Voronoi regions?

SciPy

from scipy.spatial import Voronoi
import matplotlib.pyplot as plt
import numpy as np
points = np.array([[0, 0], [1, 0], [0, 1]])
vor = Voronoi(points)
for region_index in vor.point_region:
    region = vor.regions[region_index]
    polygon = [vor.vertices[i] for i in region]
    plt.fill(*zip(*polygon), alpha=0.4)
plt.show()

A TypeError: 'NoneType' object is not iterable

B ValueError: too many values to unpack (expected 2)

C No error, plots correctly

D IndexError: list index out of range

💡 Hint

Some Voronoi regions can be empty or contain -1 indicating infinite vertices.

The region list can contain -1 which is not a valid index for vertices, causing NoneType or iteration errors when accessing vor.vertices[-1].

🚀 Application

expert

Using Voronoi diagram to find nearest neighbor regions

Given a set of points, which code snippet correctly finds the index of the Voronoi region closest to the point [3, 3]?

SciPy

from scipy.spatial import Voronoi, distance
import numpy as np
points = np.array([[1, 2], [4, 4], [5, 1], [2, 5]])
vor = Voronoi(points)
query_point = np.array([3, 3])
# Fill in code to find closest Voronoi region index

A

distances = [distance.euclidean(query_point, vor.vertices[i]) for i in range(len(vor.vertices))]
closest_index = distances.index(min(distances))
print(closest_index)

B

distances = [distance.euclidean(query_point, points[i]) for i in range(len(points))]
closest_index = distances.index(min(distances))
print(closest_index)

C

closest_index = vor.point_region[np.argmin(np.linalg.norm(points - query_point, axis=1))]
print(closest_index)

D

closest_index = np.argmin(np.linalg.norm(vor.vertices - query_point, axis=1))
print(closest_index)

💡 Hint

Voronoi regions correspond to input points via point_region attribute.

Option C correctly finds the input point closest to query_point and then gets its Voronoi region index using point_region. Other options either use vertices or do not map to regions correctly.