Voronoi diagrams in SciPy - Time & Space Complexity

Time Complexity: Voronoi diagrams

O(n \log n)

Understanding Time Complexity

We want to understand how the time to create a Voronoi diagram changes as we add more points.

How does the work grow when we increase the number of input points?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np
from scipy.spatial import Voronoi

points = np.random.rand(100, 2)  # 100 random points in 2D
vor = Voronoi(points)  # compute Voronoi diagram
    

This code creates 100 random points and computes their Voronoi diagram using scipy.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Constructing the Voronoi diagram involves building a Delaunay triangulation and then deriving the Voronoi cells.
• How many times: The sorting and triangulation steps lead to O(n \log n) operations overall.

How Execution Grows With Input

As we add more points, the time to compute the Voronoi diagram grows faster than just adding points one by one.

Input Size (n)	Approx. Operations
10	About 35 operations
100	About 700 operations
1000	About 10,000 operations

Pattern observation: The work grows roughly with n log n, so doubling points makes the work about twice as much, plus a bit more due to the log factor.

Final Time Complexity

Time Complexity: O(n \log n)

This means the time grows a bit faster than just the number of points, but not as fast as the square of points.

Common Mistake

[X] Wrong: "Computing Voronoi diagrams always takes time proportional to the square of the number of points."

[OK] Correct: The algorithm uses clever sorting and triangulation steps that keep the time closer to n log n, not n squared.

Interview Connect

Understanding how Voronoi diagram computation scales helps you explain efficiency in spatial data problems, a useful skill in many data science tasks.

Self-Check

"What if we computed Voronoi diagrams in 3D instead of 2D? How would the time complexity change?"