Delaunay triangulation in SciPy - Time & Space Complexity

Time Complexity: Delaunay triangulation

O(n log n)

Understanding Time Complexity

We want to understand how the time needed to create a Delaunay triangulation changes as we add more points.

How does the work grow when the input size grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np
from scipy.spatial import Delaunay

points = np.random.rand(1000, 2)  # 1000 random points in 2D
tri = Delaunay(points)  # compute the triangulation

This code creates a Delaunay triangulation for 1000 points in 2D space.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking and connecting points to form triangles without overlapping circumcircles.
• How many times: The algorithm processes points and edges multiple times, roughly proportional to the number of points and their neighbors.

How Execution Grows With Input

As we add more points, the number of triangles and edges grows, so the work to check and connect points grows too.

Input Size (n)	Approx. Operations
10	About 10 to 30 operations
100	About 100 to 300 operations
1000	About 1000 to 3000 operations

Pattern observation: The operations grow a bit faster than the number of points but not as fast as the square of points.

Final Time Complexity

Time Complexity: O(n log n)

This means the time needed grows a little more than linearly as we add points, but not too fast.

Common Mistake

[X] Wrong: "The time to build the triangulation grows like the square of the number of points (O(n²))."

[OK] Correct: The algorithm uses smart ways to avoid checking every pair of points, so it runs faster than that.

Interview Connect

Knowing how Delaunay triangulation scales helps you understand performance in spatial data tasks, a useful skill in many data science problems.

Self-Check

"What if we changed the points from 2D to 3D? How would the time complexity change?"