Quantum Approach to Delaunay Triangulation

SLB Quantum Use-Case for Aqora Q-Energy Hackathon I

Hosted by

SLB

Definition of Delaunay Triangulation

Delaunay triangulation is a method of connecting a set of points in a plane into triangles such that no point lies within the circumcircle of any triangle. This is known as the empty sphere criterion. Mathematically, for a set of points

P=\{p_1, p_2, \dots, p_n \}

, a triangle formed by points

(p_i,p_j,p_k)

is a Delaunay triangle if the circumcircle

C

defined by these three points contains no other points from

P

inside it (B. Delaunay, 1934).

Unique Solution to a Combinatorial Problem

Delaunay triangulation represents a unique solution to a combinatorial problem, where the number of possible triangulations can be extremely large. According to Aichholzer et al. (2016), the number of triangulations possible in

2D

is bounded between

2.631^n \leqslant T(n) \leqslant 30^n

where

T(n)

denotes the number of triangulations for

n

points in general position. This demonstrates the significant combinatorial complexity involved in triangulating a set of points.

Classical Algorithm: Bowyer-Watson Incremental Algorithm

The Bowyer-Watson algorithm is a widely used incremental method for computing the Delaunay triangulation (Bowyer, A. 1981; Watson,D. 1981). The process can be summarized as follows (for

2D

Initialization: Start with a super triangle that encompasses all points (or any other convex polygon).
Point insertion: For each point $p$ $p$ to be added:
- Identify the triangle containing $p$
- Remove triangles that violate the Delaunay condition (those that contain $p$ in their circumcircles).
- Re-triangulate the resulting boundary (cavity).
Termination: Repeat until all points have been inserted.

Complexity and Data Structures

The complexity of the Bowyer-Watson algorithm heavily depends on the order of point insertion. With a well-chosen point insertion order and the use of efficient data structures like a kd-tree (Jian-Fei Liu et al., 2013), the expected time complexity can be improved to

O(n \log(n))

Delaunay triangulation as Energy Minimization

The Delaunay triangulation minimizes a specific energy function related to the triangles formed. Specifically, it minimizes the total volume of the prisms

\sum_i v_i

under the function

z = x^2 + y^2

over the triangulation in the plane (R. Musin, 1997). This is related, to some extent, to the maximization of the minimal angle by the Delaunay triangulation. This makes this triangulation optimal for various applications (including mesh generation for physical simulations).

Given the complexity of Delaunay triangulation and its wide-ranging applications, there is a growing interest in exploring advanced computational techniques, including quantum computing. The potential of quantum algorithms to solve combinatorial problems more efficiently than classical algorithms may lead to significant improvements in Delaunay triangulation methods. This document aims to investigate these possibilities and outline the implications of utilizing quantum computing in this field.

Modeling Delaunay Triangulation as a Minimization Problem

Delaunay triangulation can be modeled as a minimization problem, as discussed by R. Musin (1997). The problem is defined by the following parameters:

Data: We have $n$ points in the plane and the four points of the bounding box (see figure below).

Step 1: Associating Binary Variables with Triangles

For

n

points, there are

\frac{n(n-1)(n-2)}{6}

possible triangles, which correspond to the binary variables in our minimization model. Each binary variable indicates whether a specific triangle is included in the Delaunay triangulation (1) or not (0).

Step 2: Writing the Energy to Minimize

The energy function

V(t)

to minimize is defined as:

V(t) = \sum_i (z_{i0} + z_{i1} + z_{i2}) a(t_i)

In this equation:

$z_{ij} = x_{ij}^2 + y_{ij}^2$ , where $(x_{ij}, y_{ij})$ are the coordinates of the $j$ -th vertex of triangle $t_i$ .
$a(t_i)$ is the area of triangle $t_i$ .

This function captures the total energy based on the geometric properties of the triangles formed by the points.

Step 3: Adding Constraints

To ensure a valid triangulation, we introduce the following constraints:

Boundary Edges: Each edge of the bounding box must have exactly one incident triangle.
Internal Edges: Each internal edge must have exactly two incident triangles.
Internal Points: Each internal point must be incident to at least three triangles.

These constraints are crucial for maintaining the integrity of the triangulation and ensuring that the resulting structure is valid according to the properties of Delaunay triangulation.

Quantum Annealing Approach

To solve this minimization problem, we employ quantum annealing using D-Wave machines. Quantum annealing leverages quantum mechanics to find low-energy states of a system, making it a suitable approach for optimizing complex combinatorial problems such as Delaunay triangulation. The ability of D-Wave systems to explore multiple configurations simultaneously can significantly enhance the efficiency of finding the optimal triangulation compared to classical methods.

By applying quantum annealing, we were able to calculate a distribution of solutions (triangulations), with the Delaunay triangulation emerging as the optimal solution that minimizes the energy described earlier. This process allows us to efficiently identify various valid triangulations, showcasing the advantages of using quantum approaches in this context.

The challenges associated with the proposed solution can be summarized in four key points:

Scalability: For $n$ points in $2D$ , we require $O(n^3)$ variables. In 3D, this complexity increases to approximately $O(n^4)$ . It is important to note that many industrial problems are often in $3D$ , or even $4D$ if we consider the time dimension.
Sparsity: In $2D$ , the number of possible triangles is bounded, specifically $\leqslant 2n$ , where $n$ is the number of points. We are dealing with a very sparse problem; in our case, with 10 points, we ended up with 1000 binary variables, while the final Delaunay triangulation consisted of only 18 triangles. This characteristic of sparsity has not been exploited in our approach.
Invalid Solutions: The proposed approach can yield solutions that are not valid triangulations, leading to intersections between segments. Usually, it happens for degenerate triangles (ones with very small area, see figure below).

Algorithmic Nature: The proposed algorithm does not possess any inherently quantum features. In other words, it could have been solved using a classical optimizer, such as IBM CPLEX.

Project Objectives

We aim to develop a quantum algorithm that addresses this geometric problem. To achieve this, several key objectives must be met:

Efficient Quantum Representation: Develop an effective quantum representation of the geometric data, specifically the coordinates $x$ and $y$ . This representation should facilitate efficient processing and manipulation of the data within a quantum framework.
Quantum Algorithm Development: Create or “innovate” a quantum algorithm for an equivalent of the empty sphere criterion. In a wider sense, the goal is to explore how to formulate a geometric problem within the quantum computing paradigm, based on its classical formulation.
Performance Metrics:
- Data Representation Efficiency: Assess how well the quantum representation of the data scales with an increasing number of points in $2D$ , and how it can be generalized to higher dimensions.
- Originality of the Quantum Algorithm: Evaluate the uniqueness of the developed quantum algorithm, noting that it is not necessarily limited to a quantum version of the empty sphere criterion.
- Validation of Solutions: Ensure that all calculated solutions are valid triangulations.
- Complexity Comparison: Demonstrate that the complexity of the quantum algorithm is at least equivalent to that of the classical algorithm.
Bonus Consideration: Investigate how well the proposed quantum algorithm can accommodate constraints. In the $2D$ case, this would involve incorporating imposed segments within the domain.

References

B. Delaunay (1934). Sur la sphère vide.
O. R. Musin (1997). Properties of the Delaunay triangulation.
Aichholzer, et al. (2016). An improved lower bound on the minimum number of triangulations.
Bowyer, Adrian (1981). "Computing Dirichlet tessellations."
Watson, David F. (1981). "Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes."
Jian-Fei Liu, et al. (2013). A new insertion sequence for incremental Delaunay triangulation.