ABSTRACT
We present an algorithm for enumerating all possible faceting arrangements of dihedrally symmetric diamond cuts. We first separate the question into enumerating crowns and pavilions. In each case, the method involves enumerating all plausible graphs within a fundamental domain, and then checking for planarity and triconnectivity using the Tutte spring embedding. Such graphs can be lifted to three dimensional convex crowns or pavilions via the Maxwell-Cremona correspondence.
1 INTRODUCTION
In this paper we explore the set of all possible dihedrally symmetric diamond cuts. The most common diamond cut is called the standard round brilliant (see Figure 1), and like most modern diamond cuts, has a crown, a girdle, and a pavilion. The crown has a horizontal central facet called the table, while the pavilion has a central vertex called the culet. The girdle of a standard round brilliant is faceted to be approximately circular. It can be modeled mathematically with a minimum of 16 facets, though it is often represented with 32 or 64. Note that as soon as additional facets beyond the minimum of 16 are added, the girdle develops a scalloped appearance.
In this paper, we will not be interested in the specific geometry of a cut, but in the abstract faceting arrangement. That is, we won’t care about specific measurements like table size, facet angles, and diameter. Rather, we restrict attention to the abstract graph isomorphism class of a cut. Once we have an enumeration of all isomorphism classes, the next task facing a diamond designer is to optimize proportions within each class. Optimizing proportions is a significant area of research in diamond cut, though it is not the subject of this paper. The interested reader will find an extensive literature for the standard round brilliant [7, 11, 12, 18]. The paper [15] analyzes diamond beauty from the perspective of human perception, and is not round brilliant specific.
The modern cutter avails himself of commercial products for evaluating cut quality and optimizing the weight within a piece of rough. The companies Sarine, Octonus, and Lexus SoftMac offer both instrumental and software support for diamond cutting. At time of publication, the Gemological Institute of America offers a cut evaluation for standard rounds and offers light performance analysis for a select group of other cuts.
We also note that the potential cut of a diamond is somewhat constrained by lattice orientation. In particular, the {1,1,1} direction (using standard lattice coordinates) is very difficult to cut and polish. However expert diamond cutters have techniques to mitigate this issue and lattice orientation is not normally considered when planning a rough.
A diamond is an example of a convex polyhedron – a convex three dimensional body with flat faces. (Non-convex diamonds, such as hearts, exist, but will not be considered here.) One naive hope in exploring possible diamond shapes would be to simply list all polyhedra in order of increasing complexity. However, the number of such polyhedra grows absurdly quickly, and most of them are not plausible gemstone shapes.
The search space can be reduced by considering the symmetry of a diamond.
1.1 SYMMETRY
The symmetry group of an arbitrary polyhedron is a finite subgroup of O(3). However, for diamonds as considered in this paper, the symmetry group is more restricted. Such diamonds have a preferred “up” direction, having been designed to be viewed perpendicularly to the table. In particular, we define the symmetry group to preserve the table setwise. Note that a symmetry of a polyhedron that fixes a face pointwise is trivial, so the set of symmetries of a polyhedron that preserves a face setwise is a subgroup of the symmetry group of the face, implying it is planar.
The finite planar symmetry groups are well known to be one of the following types: rotational Rn ≅ ℤ/nℤ for n ≥ 2, or dihedral D2n for n ≥ 1.
Groups of the first kind have no reflectional symmetries and consist of rotations by multiples of 2π/n around a center point. For example, Figure 2 depicts a diamond crown with R3 symmetry. Diamonds such as this with no reflectional symmetry are uncommon, but certainly exist. Indeed, there are diamond designs which have no symmetry at all.
Dihedral groups, D2n, have n lines of reflectional symmetry with angles of π/n between them. The composition of two reflections is a rotation, implying that diagrams with this symmetry group also have the set of rotations Rn as a subgroup. In all, there are 2n symmetries, which explains the subscript of the notation D2n. Figure 2 gives examples of D2,D4 and D8 symmetry. Note that D2n is the symmetry group of a regular polygon for n ≥ 3, with D2 and D4 being somewhat exceptional.
In this paper we will study the crowns and pavilions separately. Each will inherit the symmetry group of the parent diamond. Note that we can pair any crown and pavilion that have the same shape outline to create a diamond model, with the z-offset between crown and pavilion being an additional parameter.
1.2 GENERATING PATTERNS FROM SYMMETRY GROUPS
Consider the pictures on the left of Figure 3. The first two examples have D8 symmetry while the second two have D16 symmetry. The lines of reflection cut the plane into 8 or 16 sectors, and the diagrams are completely determined by the intersection with a chosen sector. We call the choice of such a sector a fundamental domain. More generally for planar reflection groups, a fundamental domain is defined as the closure of a choice of connected component of the complement of the reflection lines. Fundamental domains can also be defined for more general group actions, but we will not need that in this paper.
The diamond’s crown or pavilion is drawn as a graph in the plane. We call the intersection of the graph with a fundamental domain a generating graph, since rotated and reflected images of this will fill out (i.e. generate) the whole graph.
It will follow from Theorem 3 that a generating graph for a diagram with D2n symmetry (n ≥ 3), can be used to generate a dihedrally symmetric diamond of any order ≥3. This phenomenon is illustrated with the generalized standard round brilliants and princesses in Figure 4.
Theorem 3 leads to the somewhat surprising conclusion that there is a 1-1 correspondence between the set of facet arrangements of diamonds with dihedral symmetry group D2n and D2m for any n, m ≥ 3.
2 FROM TWO TO THREE DIMENSIONS
A classical theorem of Steinitz [16, 17] states that convex 3D polyhedral are in 1−1 correspondence with triconnected planar graphs (also called Schlegel diagrams or c-nets.) A connected graph is said to be triconnected if deleting any set of ≤2 vertices leaves the graph connected. Ziegler [23] collects many proofs of Steinitz’s theorem, including one, the Maxwell-Cremona correspondence, which we make use of in Theorem 2. See the notes to Chapter 4 of Ziegler [23] as well as videos by Sheehy [13,14].
Thus one approach to enumerating diamond cuts is to enumerate triconnected planar graphs, and it is even the case that one could enumerate dihedrally symmetric Schlegel diagrams to recover dihedrally symmetric polyhdera [9]. However this would not take advantage of the special geometry of diamonds, that they decompose into crown, girdle, and pavilion, and would include many implausible diamond cuts.
Instead, we will consider diagrams of crowns and pavilions separately and determine when they can be embedded in the plane so that some assignment of z coordinates to each vertex gives a valid 3D geometry.
2.1 TRUSSES AND LIFTING DIAGRAMS
Let us consider a two dimensional picture of a diamond crown or pavilion wireframe (the 1-skeleton of the polytope). In order to convert this to a three dimensional wireframe, we need to assign a height (z-coordinate) to each vertex. The assignment of heights needs to create coplanar facets, while coplanarity of the vertices around the boundary is not necessary in order to form a diamond crown or pavilion.
In fact, as an illustration of this last point, in the 16 girdle facet model of the standard round brilliant, there are two types of vertices on the boundary of both crown and pavilion, which can be at different heights (Figure 5). The boundary vertices of a princess diamond, on the other hand, must all have the same height by symmetry.
Definition 1. We say a planar graph is liftable, if there is an assignment of heights to the vertices such that the lifted vertices in each bounded face are coplanar. Such an assignment will be called a lift.
We define a truss to be a lift of a 2D graph, and say it is convex if
- the outer boundary of the 2D graph is convex,
- the lifted facets meet in mountain rather than valley folds.
Let z = k be a plane such that k is less than the height of every lifted vertex. Form a polytope as the set of all points underneath the truss and above this plane. The above conditions ensure that this polytope is convex.
When enumerating diagrams, it will be most convenient if we only have to consider abstract graph types rather than particular embeddings, though we will need to keep track of the cycle of edges that forms the outer boundary. Note that every truss gives rise to an abstract planar graph with a specified cycle representing the outer edges.
Definition 2.
- A pair (G,C) consisting of a connected graph G and a specified cycle C ⊂ G will be called a circuited graph.
- All maps of circuited graphs to ℝ2 will be assumed to embed the specified cycle as a convex polygon, while the remaining vertices and edges will be mapped to the interior of this polygon.
- We say a circuited graph is liftable if it has a planar embedding which is liftable to a convex truss.
There is an analogue of Steinitz’s Theorem for trusses, but we need another definition to state it.
Definition 3. We say a circuited graph (G,C) is boundary triconnected if deleting any set of ≤ 2 vertices from G has the property that all connected components contain vertices from C.
Remark. The necessity of this formulation can be seen by considering the 8 vertex graph consisting of a square with each side bisected and 4 edges added to create a new square, rotated by 45 degrees, inside the first one. This is not triconnected and so does not correspond to a polytope, but it is liftable and could conceivably form the crown of a diamond.
Indeed, a top down view of such a graph appears in Figure 6 (Fig 22), a list of different diamond cuts in Diderot’s encyclopedia published in the late 1700s [6].
Before we state the main theorem, that boundary triconnected trusses are liftable, we take a slight detour to discuss the Tutte embedding.
2.2 TUTTE ON HOW TO DRAW A GRAPH
Let (G,C) be a circuited graph. Assign each internal edge e a positive weight se called its spring tension. Embed the outer cycle in the plane in any convex way and consider the vertices in this cycle to be immovable. Now think of the graph as being a network of nodes connected by springs and let it settle into equilibrium. In the equilibrium state, the sum of forces acting on each internal vertex will be zero. That is, if we scale each edge, thought of as a vector connecting its endpoints, by its spring tension, and then add all the edges outgoing from a single internal vertex, they should sum to zero as a vector. The positions of the internal vertices are easily calculated by solving the resulting system of equations.
If (G,C) is an abstract circuited graph, S is a set of spring tensions on the edges not in C, and φ: C →ℝ2 is a convex embedding of the boundary cycle, we denote the resulting image of the graph in the plane by Tutte(S,φ)(G,C), or just TutteS (G,C) if the boundary embedding is clear from context.
Theorem 1 (Tutte [19,20]). A circuited graph, (G,C), has a planar embedding and is boundary triconnected if and only if G has no interior bivalent vertices and Tutte(S,φ)(G,C) is an embedded graph in the plane, for any choice of positive spring tensions and convex boundary embedding.
We note that Tutte uses the term “3-linked with C” for what we call “boundary triconnectivity.”
One way that a graph can fail to be (boundary) triconnected is if it has a univalent vertex. When one puts a spring tension on the incident edge, the edge will shrink to zero, so Tutte(S,φ)(G,C), will fail to be embedded. Indeed the same reasoning applies if there is a cut vertex. The side of the cut vertex that fails to intersect C will contract to a point. Suppose you have two vertices whose deletion disconnects the graph into two components and one of the components does not intersect C at all. That means this entire component will shrink toward a line segment connecting the two points when positive spring tensions are applied. Therefore, Tutte(S,φ)(G,C) will again fail to be connected as long as the component was not itself linear (i.e. formed from a chain of bivalent vertices). So we conclude that the Tutte map will detect the failure of boundary triconnectivity except for the presence of interior bivalent vertices.
Theorem 2. A circuited graph is liftable iff it has a planar embedding and is boundary triconnected.
Moreover, if the circuited graph has symmetry group 𝒢, the truss can be constructed to have the same symmetry group.
Proof: First suppose that a circuited graph is liftable. Projecting a truss to the xy plane yields an embedding, so we need only show that a convex truss is boundary triconnected. Form the polytope as described after Definition 1. This polyhedron is triconnected. Now choose a pair of vertices in the truss, and suppose they disconnect it into two pieces. Since the whole polytope is triconnected, each piece must be connected to the edge of the truss for otherwise the polytope minus the two vertices would be disconnected. Hence the truss is boundary triconnected.
Next suppose that we have a boundary triconnected circuited graph with a planar embedding. Then by Theorem 1, the Tutte map yields an embedding where all the spring tensions are in equilibrium. Once the diagram is embedded, the standard proof of the Maxwell-Cremona correspondence goes through to lift to a truss. See Crapo&Whiteley [4,5].
Now suppose that a group 𝒢 acts on a boundary triconnected circuited graph (G,C) by automorphisms. Embed C as a regular polygon in the plane, and set all internal edge tensions equal to 1. Then the Tutte embedding will also have 𝒢 symmetry. We can choose a symmetric lift as follows. According to the Maxwell-Cremona correspondence (see [13,14]), lifts of a diagram are controlled by the spring tensions and a chosen facet normal. The spring tensions are used to construct a “reciprocal diagram,” while different choices of facet normal translate the reciprocal diagram around the plane. In order to get a symmetric lift, we center the reciprocal diagram on the origin.
The last paragraph of the proof implies that for symmetric graphs, the space of symmetric 3D realizations (with fixed (x,y) coordinates of the outer boundary and discounting vertical shifts) has the same number of dimensions as independent spring tensions plus the degrees of freedom in repositioning the reciprocal diagram while respecting the symmetry group. For D4 and higher, the reciprocal diagram must be centered on the origin, corresponding to the intersection of the reflection lines. For D2, the reciprocal diagram can be centered anywhere along a line through the origin parallel to the unique line of symmetry, adding one dimension to the parameter space. For the trivial group, there are two extra degrees of freedom. For any nontrivial rotational group Rn, there are no extra degrees of freedom. So parameter space has the same number of dimensions as interior edge orbits under the group action, possibly with the addition of 1 or 2 parameters for the groups D2 and D0 = R0 respectively. We have collected the dimensions of parameter spaces for three diamond faceting arrangements in Figure 7.
It is worth pointing out that Tutte’s method of drawing planar graphs is not the only one. A particularly powerful circle packing method is due to Mohar [10].
2.3 TRUSS RECOGNITION ALGORITHM
If we have a method to detect when the Tutte map is an embedding, then we can use the preceding section to create an algorithm for detecting trusses. One could simply check all pairs of edges of the Tutte map of a circuited graph for intersections, but we prefer to use a more combinatorial approach using ribbon graphs. It has the added benefit of detecting the faces of a planar graph, which is necessary information to implement the Maxwell-Cremona lifting algorithm for creating a 3D model.
A ribbon graph is defined to be an abstract graph with a cyclic order of incident edges at each vertex. A ribbon graph has a thickening to an oriented surface with boundary components, which is defined by putting an oriented disk at each vertex and gluing long thin rectangles along the edges using the cyclic order to indicate where they should be glued. (In fact, some authors only consider the thickened object to be a ribbon graph.)
One can read off the boundary components of the ribbon thickening by doing walks along the graph where, at each vertex, one leaves on the edge that comes next in the cyclic ordering after the edge one entered on. If you have a graph mapped (not necessarily embedded) to the plane
such that no edges emanate from a vertex in exactly the same direction, then there is an induced ribbon graph structure on the graph. One defines the cyclic order at each vertex to be induced by the plane’s orientation. Figure 8 shows the ribbon graph boundary components in a particular example. Many readers fail to notice that the two edges in the middle intersect, so be aware!
If a circuited graph is planar, then there is a bijection between boundary components and planar faces, so Euler’s formula v−e+ f = 2 must hold. (v,e,f being the number of vertices, edges, and faces, including the outer unbounded face, respectively.) Conversely, if v−e+ f = 2, the ribbon thickening is a sphere with holes, and gluing in disks to those holes gives an embedding of the graph in the sphere, where the specified cycle bounds a face. Designating that face as the unbounded face gives a planar embedding of the circuited graph. Hence the Tutte map must also be planar.
Summarizing, we get a truss recognition algorithm as follows. First check if the circuited graph is connected and that it has no bivalent vertices. If it passes these checks, consider a Tutte map of the graph. Check that it has no coincident vertices (within some tolerance), and that no edges emanate from a single vertex in the same direction (within some tolerance). If it passes these checks, thicken the graph, count the number of boundary components, and check if v−e + f = 2. If so, then it is a truss. Otherwise it is not.
3 ENUMERATION
Recall that any dihedrally symmetric diagram in the plane has a fundamental domain which is a sector of the plane bounded by a vertex at the diamond’s center, and two infinite rays, which we call walls and recall that the intersection of the planar graph with a fundamental domain is called the generating graph of the diagram. Note that the generating graph can have “half edges” which intersect either of the two boundary walls of a fundamental domain in right angles. This is illustrated in Figure 12. An edge emanating from vertex 1 meets the right wall, and in order to form a
valid edge upon reflection through the wall, must meet it at a right angle. Every diamond will have two generating graphs, one for the crown and one for the pavilion. Pavilion generating graphs will have a vertex at the top corner of a fundamental domain, corresponding to the culet, while crown generating graphs will not have a top corner vertex.
In order to systematically enumerate diamond crowns and pavilions with D2n-symmetry (n ≥ 3), we enumerate generating graphs. We distinguish types of graphs based on the combinatorics of the outer boundary of the generating graph.
The simplest situation is where there is a single exterior vertex in a fundamental domain, lying along one of the walls (see the princess crown and pavilion in Figure 3). We call diamonds with this property simple.
The next simplest situation is when there are two exterior vertices in a fundamental domain, one per wall. This occurs in the round brilliant crown and pavilion. We call diamonds with this property standard.
There could also be additional vertices along the bottom boundary of the generating graph, representing the outer edge of the diamond. This is evident in Figure 2 for the marquise diamond with symmetry group D4. Cushion diamond cuts can have D8 symmetry with such extra boundary
vertices (Figure 9).
We make the following additional assumption:
The b1 and b2 vertices are not bivalent.
Note that Diderot’s Fig 22 in our Figure 6 does give an example of a bivalent b1. So this is a nontrivial restriction.
It follows from the just stated assumption that in the simple and standard cases, the diagram must be triconnected, not merely boundary triconnected. Indeed the only way a simple or standard graph can be boundary triconnected but not triconnected is if b1 (or b2) connects to itself across a line of reflection. This will have the effect of cuting off a little triangular flap, as in the Diderot example, and will thus have a bivalent vertex.
For simplicity, we will restrict attention to simple and standard diamond cuts for the remainder of this paper. The techniques we present generalize fairly easily to the case of any number of vertices along the outer boundary of a fundamental domain. We suggest this to an interested researcher as a nice topic for further exploration.
For simple crowns and pavilions, we assume the outer vertex is on the right-hand wall, and label it b2. For standard crowns and pavilions, we label the outer vertices b1 and b2 for the left and right wall respectively. For a pavilion of either variety, the top corner of the chosen fundamental domain will have a vertex, which we label c.
Before we continue, we pause to prove that generating graphs are agnostic to symmetry order for n ≥ 3.
3.1 SYMMETRY ORDER
A generating graph can be used to generate graphs of any D2n-symmetry, n ≥ 3, by interpreting it in a sector of the correct angular width.
Theorem 3. Let G be a connected generating graph, and let Gn be the abstract circuited graph formed with D2n symmetry. Then Gn is planar and boundary triconnected for all n ≥ 3 iff G3 is planar and boundary triconnected.
Proof: Regarding planarity, note that Gn is planar iff the restriction to the sector is planar, a condition which does not depend on the sector’s angular width.
Next we show that a graph G3 is biconnected iff Gn is biconnected for any n ≥ 3. More specifically, we show that the existence of a cut vertex for any n is equivalent to the existence of one for n = 3.
Let us fix the following conventions for a connected graph G. Let c be a vertex of the graph. If G\{c}, considered as a topological space, is not connected, we say c is a cut vertex. The connected components of G\C where C is the set of cut vertices, are called the biconnected components. Note that according to this convention, the cut vertices themselves do not belong to biconnected components, and the biconnected components have open edges.
Because the biconnected components of G are disjoint, if σ ∈ Aut(G), g is a biconnected component, and (σ·g) ∩g ≠ ∅, then σ · g = g setwise. (*)
Now consider the circuited graph Gn. There must exist at least one biconnected component, g, which is adjacent to only one cut vertex, c, and which does not meet the graph’s exterior circuit. If g meets a wall away from c, then g overlaps with its reflection, so by (*), g is symmetric with respect to that wall. Hence c must also lie on the wall. If g meets any more walls, since it is symmetric in those walls, the vertex c will have a reflection that also meets g, contradicting that g meets at most one cut vertex. Thus g is contained in at most two adjacent fundamental domains. This implies that c will correspond to a cut vertex in any of the generated graphs Gk , k ≥ 3.
For triconnectivity we argue as follows. Suppose G is a biconnected graph. Then it can be decomposed into triconnected components [8], where a triconnected component is defined to be a subgraph which is triconnected and is not contained in a larger triconnected subgraph. Every edge belongs to a unique triconnected component, but vertices may belong to multiple components. We call the vertices of a component that belong to multiple components boundary vertices, and the rest of the component its interior.
Then Aut(G) acts on the sets of interiors of triconnected components. If σ ∈ Aut(G) and g is the interior of a triconnected component, then (σ · g) ∩ g ≠ ∅ implies that σ · g = g setwise as before.
Suppose one of the graphs Gn is not boundary triconnected. We can always find a triconnected component, g, with 2 boundary vertices whose interior does not meet the exterior circuit. We claim g is in at most two adjacent fundamental domains. Otherwise, suppose that g lies in three adjacent fundamental domains. Let r1 and r2 be reflections corresponding to the two interior walls separating these domains. Then I claim g is fixed setwise by both r1 and r2. If g doesn’t actually hit one of the two interior walls, then it is not connected, a contradiction. If it does hit a wall, there are two cases. It does so in the interior of g, then the point where it does is fixed by the associated reflection r, meaning that r fixes the entire component setwise. If g meets the wall in one of its two boundary vertices and nowhere else, then this vertex locally separates g, a contradiction.
But now notice that no matter how the boundary vertices are positioned, they can’t be invariant setwise under both r1 and r2.
Thus a nontrivial triconnected component will be present in G3 as well, and we conclude that the boundary triconnectivity of Gn is equivalent to that of G3.
3.2 FIRST STEPS
To illustrate how the enumeration algorithm works, let’s look at how to generate simple crowns and pavilions with small numbers of vertices.
Suppose there is one vertex in our fundamental domain aside from the boundary vertex b2. If that vertex lies at the top corner c, then it must connect to the boundary vertex by a single line. The generated graph represents a pyramid when lifted to 3D, which is the simplest possible pavilion. The generating graph is given at the top of the leftmost column of Figure 10, and three lifts of different symmetry order are depicted below it.
If the vertex lies along the right wall, it must connect to b2, but it must also connect to (a reflected copy of) itself, meaning it has an edge emanating to the left and meeting the left wall at a right angle. This leads to the second column of Figure 10, representing the simplest possible crown. Similarly, if the vertex is on the left wall, it must connect to itself and to b2, which yields the crowns in the fourth column. Finally, if the vertex lies in the middle, it needs to connect to itself both to the left and to the right, leading to the crowns in the third column. Switching to standard graphs leads to the diagrams in Figure 11.
In order to mechanize this process, we implement the Tutte embedding and truss recognition algorithm.
3.3 THE ALGORITHM
As we saw earlier, we are considering generating graphs that may or may not have a vertex at the top corner of the chosen fundamental domain (labeled c if it exists), and it may or may not have boundary vertices on either of the two walls of the fundamental domain, labeled b1 and b2.
The example in Figure 12 details how we encode generating graphs. The generating graph is pictured on the right. This is a simple crown, with only a b2 vertex. There are three types of vertices other than this boundary one. The two vertices labeled 1 and 2 lie on the left wall. We therefore call these “L” vertices. The vertex 3 is in the interior (or middle) of the fundamental domain, so we call it an “M” vertex. Finally, vertex 4 lies on the right-hand wall, so is called an “R” vertex.
Let nL,nM , and nR denote the number of vertices of each kind.
In Figure 12, the graph is encoded by the following data:
- The ordered triple (nL,nM ,nR) = (2,1,1).
- The edge connections of the vertices 1,...,4:
{1,3},{2,3},{3,4} - The edges that connect vertices with their reflections:
{1,1},{3,3,−1}
Here the−1 indicates that the edge is reflected through the left wall.
If the edge went through the right wall, we would use the notation
{3,3,+1}.
4. The list of vertices the corner attaches to, in this case {2,4}.
Similarly, if there are other boundary vertices we list the vertices those connect to as well. For example, referring to Figure 3, we have
Princess Crown | |
(nL,nM ,nR) | (1,1,1) |
(b1, b2, c) | (F,T,F) |
| edges | {{1,3},{1,2},{2,3},{2,2,−1}} |
| b2 connections | {2} |
Princess Pavilion | |
| (nL, nM , nR) | (4,0,1) |
| (b1, b2, c) | (F,T,T) |
| edges | {{1,2},{2,3},{3,4}} |
| b1 connections | {1,2,3,4} |
| b2 connections | {1} |
| Round Brilliant Crown | |
| (nL, nM , nR) | (1, 0, 1) |
| (b1, b2, c) | (T,T,F) |
| edges | {{1,2},{2,2}} |
| b1 connections | {1} |
| b2 connections | {1} |
| Round Brilliant Pavilion | |
| (nL, nM , nR) | (1, 0, 0) |
| (b1, b2, c) | (T,T,F) |
| edges | {} |
| b1 connections | {1} |
| b2 connections | {1} |
c connections | {1} |
Given such combinatorial data we can reconstruct the embedded generating graph as follows. First choose some n ≥ 3 and generate an abstract graph from the generating graph with symmetry group D2n. We have a specified outer cycle, so we can apply the Tutte embedding. Finally, we restrict to a fundamental domain to get an embedded generating graph.
Fix nL, nM , nR as well as the boundary vertex booleans b1, b2 , c which indicate whether the corresponding vertex exists or not. In order to find all generating graphs with these data, we list all possible feasible ways of abstractly connecting all the relevant vertices, then checking them all for planarity, triconnectivity and duplicates. We reduce the number of graphs that need to be searched by imposing some constraints that embedded graphs must satisfy:
- The subgraph spanned by each of the L or R vertices has to be a subgraph of a linear chain.
- The b2 vertex connects to at most one R vertex, while a b1 vertex will connect to at most one L vertex. A c vertex will connect to at most one vertex each of the L and R vertex sets.
So consider a graph TGraph(nL, nM , nR) on vertices of type L,M,R with edges in the following classes:
- A linear chain on the L vertices. (edge count: max(nL−1,0).)
- all edges connecting L vertices to M and R vertices. (edge count: nL(nM + nR).)
- all edges connecting M vertices to other M vertices and R vertices. (edge count:
- A linear chain on the R vertices. (edge count: max(nR−1,0).)
- All self edges on the L and R vertices. (edge count: nL + nR.)
- Two types of self edges (k,k,1) and (k,k,−1) on the M vertices. (edge count: 2nM .)
Next we consider graphs formed by all subsets of these edges, forming a list called abcBoolSets.We store each member of abcBoolSets as an array of booleans indicating whether a given edge is included or excluded from the graph.
We also define
- b1BoolSets encodes all possible sets of edges connecting b1 to the graph’s interior vertices. Its members are arrays of nL + nM + nR booleans, limited to at most one T in the first nL slots.
- b2BoolSets encodes all possible sets of edges connecting b2 to the graph’s interior vertices. Its members are arrays of nL + nM + nR booleans, limited to at most one T in the last nR slots.
- centerBoolSets encodes all possible sets of edges connecting cto the graph’s interior vertices. Its members are arrays of nL + nM + nR booleans, limited to at most one T in the first nL slots and one T in the last c.
- Booleans cb1 and cb2 indicate whether there are edges connecting c to bi.
Next we fix the size of elements of abcBoolSets, b1BoolSets, b2BoolSets and centerBoolSets to be j,k,l,m respectively (iterating over all possibilities). For each element of these, we form a concatenated string of booleans. This gives us a list boolGraphSet.
The next stage in the process is to remove duplicates caused by different labelings of the same graph. We consider the list of permutations XnL nM nR = SnL ×SnM ×SnR \{id}, i.e. the nontrivial permutations that respect the vertex types. Each permutation σ acts on a boolean array in g ∈ boolGraphSet by computing the action on T(nL,nM ,nR) and the edges coming from b1, b2 and c. In some cases, an edge in g when acted on by σ will not lie in T(nL,nM ,nR), which means this is not a valid relabeling. If the relabeled graph is valid, we call the result g.σ.
The algorithm for removing duplicates consists of going through every element of boolGraphSet, applying the permutations g ∈ XnL nM nR and removing valid results g.σ. In addition to removing duplicate graphs this algorithm will also remove graphs with nontrivial automorphisms. This is okay and actually desirable because any such generating graph will fail to either be connected or triconnected.
After applying the duplicate removing algorithm, we check each generating graph for connectivity using depth first search.
Next, relying on Theorem 3, each generating graph is generated into a graph with 3-fold symmetry. The Tutte map is then applied and the truss recognition algorithm is used to check if it is a truss. If not, it is discarded.
The remaining graphs are written to a file.
3.4 ALGORITHMIC COMPLEXITY
This is clearly an algorithm of exponential complexity in that it requires us to look at all subsets of edges of a certain master graph and iterate through all of these. We argue that, in fact, the number of D2n-symmetric simple and standard graphs is expected to be exponential in the number of vertices, implying that exponential complexity is unavoidable.
One reason to expect exponential complexity is Tutte’s beautiful result [21] that the set of rooted planar maps (which allow multi and self edges) with n edges is given by the unexpectedly simple formula
where a map is said to be rooted if one face is specified as the root. This at least hints at exponential complexity for our simple and standard graphs. More to the point, Tutte also considered rooted c-nets, which have the additional condition of triconnectivity. He proves that the number of rooted c-nets with n edges is asymptotically equal to
Although both of these numbers are in terms of edge count rather than vertex count, and refer to general graphs, rather than the special dihedrally symmetric ones we’ve been considering, the point of complexity
still stands.
Even though exponential complexity is unavoidable, there exist algorithms and software tools that work extremely well in practice. For example, Tutte’s methods actually give a generating function and an effective method of enumeration. See [1] for more analysis with generating functions. On the software side, Brinkman and McKay’s program plantri [3] efficiently enumerates some classes of planar graphs. See also the virtual environment CaGe [2]. The particular dihedrally symmetric case we restrict to in this paper does not seem to have been previously considered in the literature.
4 RESULTS AND TABLE
In this section we tabulate the results of the algorithm for simple or standard crowns and pavilions. We begin by listing the simplest examples as measured by the number of vertices in a fundamental domain. A generating graph needs to have at least one vertex on the boundary, and if the truss is not going to simply be a flat plane with no 3D geometry, there needs to be at least one other vertex. Hence we start with a fundamental domain containing 2 vertices.
4.1 Two vertices
There are four generating graphs with two vertices, each listed at the top of Figure 10. There is one simple pavilion and three simple crowns of the form (0,0,1), (0,1,0) and (1,0,0) respectively. The remaining rows of the diagram give diagrams with 4−,5−and 8-fold symmetry cf. Theorem 3.
4.2 Three vertices
Next we list generating graphs with 3 vertices, organized by which of the three corner vertices b1, b2, c are present.
Case 1: All three of b1, b2, c are filled. Then there is no other vertex in a fundamental domain, yielding a standard pavilion which is just a pyramid on a 2n-gon.
Case 2: Only b1, b2 are filled. This yields standard crowns with one non-corner vertex in a fundamental domain, so they must be of type (1,0,0),(0,1,0), or (0,0,1). There is one of each of these types, though
the last one is a rotation of the first one.
Case 3: Only b2 and c are filled, we get a simple pavilion with one extra non-corner vertex. There are 7 of these, three each of types (1,0,0), (0,1,0) and one of type (0,0,1).
Case 4: Only b2 is filled, we get a simple crown, with two extra non-corner vertices. There are 33 of these as summarized in this table:
Simple Crowns | ||||||
200 | 020 | 002 | 110 | 101 | 011 | total |
3 | 6 | 1 | 9 | 7 | 7 | 33 |
In Figures 13 and 14, the 4- and 5-fold lifts of the generating graphs of this section are listed.
4.3 FOUR VERTICES
The crown and pavilion graphs with 4 vertices are of the following forms:
- Simple crowns with three extra vertices:
Simple Crowns | ||||||||||
| 300 | 030 | 003 | 120 | 210 | 102 | 201 | 012 | 021 | 111 | total |
| 5 | 56 | 1 | 102 | 51 | 25 | 35 | 25 | 80 | 115 | 415 |
(Figure 15)
Simple pavilions with two extra vertices:
Simple Pavilions | ||||||
200 | 020 | 002 | 110 | 101 | 011 | total |
5 | 28 | 1 | 33 | 17 | 17 | 101 |
(Figure 16)
- Standard crowns with two extra vertices:
Standard Crowns | ||||||
200 | 020 | 002 | 110 | 101 | 011 | total |
3 | 16 | 3 | 19 | 13 | 19 | 73 |
See Figure 17 for 8-fold lifts of standard crowns with ≤ 4 vertices in a fundamental domain.
Standard pavilions with one extra vertex:
Standard Pavilions | |||
| 001 | 010 | 100 | total |
| 3 | 9 | 3 | 15 |
See Figure 18 for 8-fold lifts of standard pavilions with ≤ 4 vertices in a fundamental domain.
4.4 MASTER TABLE OF RESULTS
Figures 19 and 20 depict master tables of computational results. We set a limit of nL +nM +nR = 6 and list all triplets such that nL +nM +nR ≤ 6. For each triplet, we consider the four types of graphs determined by whether it is simple or standard and whether it is a crown or pavilion. Thus for example, there is 1 simple crown of type (0,0,4), 7 standard crowns of the same type, 1 simple pavilion, and 9 standard pavilions. Entries with a weather symbol were not computed at time of publishing. The symbols indicate difficulty of computation starting at ☼ which means less than 31.6 million graphs that need to be checked, then proceeding,⛅️, ☁️, ☁︎, ⛆, 🌧️, 🌨️, ⛈, with each one being 10 times the previous one, ending at 316 trillion graphs needing checking.
All entries were computed using C# code implementing the algorithm outlined in Section 3.2. Refactoring in C or C++ would provide a performance boost.
4.5 Odds and ends
There are a few patterns that stand out in the data. In order to discuss these, we define functions C0(a,b,c), P0(a,b,c), which count the number of simple crowns and pavilions of type (a,b,c), and C(a,b,c), P(a,b,c) which count the number of standard crowns and pavilions of type (a,b,c).
Proposition 4. The following equalities hold.
- C(a,b,c) = C(c,b,a) and P(a,b,c) = P(c,b,a).
- C0(0,0,n) = P0(0,0,n) = 1, C(0,0,n) = 2n−1, and P(0,0,n) = 2n+ 1
- C0(n,0,0) = C(n,0,0) = 2n−1. P0(n,0,0) = 2n+ 1. C(n,0,0) = 2n+ 1
- P0(1,0,n) = P0(0,1,n) and C0(1,0,n) = C0(0,1,n).
Proof: The first point follows because the vertices b1 and b2 can be interchanged. Here is a good point to note that the involution given by reflection of the diagram through the perpendicular bisector of b1,b2 acts on the sets counted by C(c,b,c) and P(c,b,c). Graphs fixed by this involution have a a higher order D2n+2 symmetry, while the other graphs are counted twice up to isomorphisms that allow boundary vertex permutation.
The fact that C0(0,0,n) = P0(0,0,n) = 1 can be seen as follows. There are n vertices lined up on the right hand wall. Each vertex can connect to the one above and below it as well as to itself across the left wall. All of the edges between consecutive vertices on the wall need to be filled in order for the graph to be connected. Moreover, since the vertex degrees need to be at least 3, the self-edges also need to be in place. Hence there is a unique such graph.
To see that C0(n,0,0) = 2n−1, let v0,...,vn be the list of vertices on the left wall, where the indices are in increasing order as you move down the wall. Given a generating graph on these, let vk be the maximal vertex that has a self-edge (which must cross the right hand wall). At least one such self edge is necessary or else the boundary vertex b2 would meet the diamond’s table, so the graph would not be triconnected. Once some vk has a self edge, all vertices with i < k must also have self edges for degree reasons. If k = n, then the graph is determined, each vk has a self-edge, each vi is connected to vi+1, and finally vn is connected to b2. Otherwise, consider the vertices with i > k. They must all connect to b2 for degree reasons and moreover the entire set of n vertices must be connected in a linear chain. Finally, the edge connecting b2 with vk may or may not be present, giving two options. In total we have 2(n−1)+1 = 2n−1 possible graphs.
The other equalities in point 3 are proved similarly.
The equalities in the last point come from expanding the L-vertex to an edge that crosses the left wall.
Proposition 5. The sequence C0(0,n,0) is equal to the number of c-nets with 3 outer vertices and n−3 inner vertices, which is OEIS sequence A285165. Our results match those of [1] within the calculated range.†
Sketch of proof: Given a C0(0,n,0) type generating graph, discard the bottom edge and introduce two new vertices that connect to all of the edges meeting the left and right walls, respectively. This gives us a planar graph with three outer vertices when we count the lower right boundary point of the fundamental domain.
We leave the reader with the following conjecture.
Conjecture 1. The number of simple crowns of type (1,0,n) is given by
C0(1,0,n − 1) = ⅓(4n3 + 6n2 + 8n + 3),
which is sequence A001845 in the OEIS.
Jim Conant is a Senior Research Mathematician at the Gemological Institute of America in Carlsbad, where he leads computational and geometric investigations into diamond cut quality, virtual facet patterns, and light-performance modeling. His work integrates advanced mathematics, computational geometry, and optical simulation to help develop the next generation of data-driven cut-grading and design tools used across the diamond industry.
ABSTRACT
We present an algorithm for enumerating all possible faceting arrangements of dihedrally symmetric diamond cuts. We first separate the question into enumerating crowns and pavilions. In each case, the method involves enumerating all plausible graphs within a fundamental domain, and then checking for planarity and triconnectivity using the Tutte spring embedding. Such graphs can be lifted to three dimensional convex crowns or pavilions via the Maxwell-Cremona correspondence.
1 INTRODUCTION
In this paper we explore the set of all possible dihedrally symmetric diamond cuts. The most common diamond cut is called the standard round brilliant (see Figure 1), and like most modern diamond cuts, has a crown, a girdle, and a pavilion. The crown has a horizontal central facet called the table, while the pavilion has a central vertex called the culet. The girdle of a standard round brilliant is faceted to be approximately circular. It can be modeled mathematically with a minimum of 16 facets, though it is often represented with 32 or 64. Note that as soon as additional facets beyond the minimum of 16 are added, the girdle develops a scalloped appearance.
In this paper, we will not be interested in the specific geometry of a cut, but in the abstract faceting arrangement. That is, we won’t care about specific measurements like table size, facet angles, and diameter. Rather, we restrict attention to the abstract graph isomorphism class of a cut. Once we have an enumeration of all isomorphism classes, the next task facing a diamond designer is to optimize proportions within each class. Optimizing proportions is a significant area of research in diamond cut, though it is not the subject of this paper. The interested reader will find an extensive literature for the standard round brilliant [7, 11, 12, 18]. The paper [15] analyzes diamond beauty from the perspective of human perception, and is not round brilliant specific.
The modern cutter avails himself of commercial products for evaluating cut quality and optimizing the weight within a piece of rough. The companies Sarine, Octonus, and Lexus SoftMac offer both instrumental and software support for diamond cutting. At time of publication, the Gemological Institute of America offers a cut evaluation for standard rounds and offers light performance analysis for a select group of other cuts.
We also note that the potential cut of a diamond is somewhat constrained by lattice orientation. In particular, the {1,1,1} direction (using standard lattice coordinates) is very difficult to cut and polish. However expert diamond cutters have techniques to mitigate this issue and lattice orientation is not normally considered when planning a rough.
A diamond is an example of a convex polyhedron – a convex three dimensional body with flat faces. (Non-convex diamonds, such as hearts, exist, but will not be considered here.) One naive hope in exploring possible diamond shapes would be to simply list all polyhedra in order of increasing complexity. However, the number of such polyhedra grows absurdly quickly, and most of them are not plausible gemstone shapes.
The search space can be reduced by considering the symmetry of a diamond.
1.1 SYMMETRY
The symmetry group of an arbitrary polyhedron is a finite subgroup of O(3). However, for diamonds as considered in this paper, the symmetry group is more restricted. Such diamonds have a preferred “up” direction, having been designed to be viewed perpendicularly to the table. In particular, we define the symmetry group to preserve the table setwise. Note that a symmetry of a polyhedron that fixes a face pointwise is trivial, so the set of symmetries of a polyhedron that preserves a face setwise is a subgroup of the symmetry group of the face, implying it is planar.
The finite planar symmetry groups are well known to be one of the following types: rotational Rn ≅ ℤ/nℤ for n ≥ 2, or dihedral D2n for n ≥ 1.
Groups of the first kind have no reflectional symmetries and consist of rotations by multiples of 2π/n around a center point. For example, Figure 2 depicts a diamond crown with R3 symmetry. Diamonds such as this with no reflectional symmetry are uncommon, but certainly exist. Indeed, there are diamond designs which have no symmetry at all.
Dihedral groups, D2n, have n lines of reflectional symmetry with angles of π/n between them. The composition of two reflections is a rotation, implying that diagrams with this symmetry group also have the set of rotations Rn as a subgroup. In all, there are 2n symmetries, which explains the subscript of the notation D2n. Figure 2 gives examples of D2,D4 and D8 symmetry. Note that D2n is the symmetry group of a regular polygon for n ≥ 3, with D2 and D4 being somewhat exceptional.
In this paper we will study the crowns and pavilions separately. Each will inherit the symmetry group of the parent diamond. Note that we can pair any crown and pavilion that have the same shape outline to create a diamond model, with the z-offset between crown and pavilion being an additional parameter.
1.2 GENERATING PATTERNS FROM SYMMETRY GROUPS
Consider the pictures on the left of Figure 3. The first two examples have D8 symmetry while the second two have D16 symmetry. The lines of reflection cut the plane into 8 or 16 sectors, and the diagrams are completely determined by the intersection with a chosen sector. We call the choice of such a sector a fundamental domain. More generally for planar reflection groups, a fundamental domain is defined as the closure of a choice of connected component of the complement of the reflection lines. Fundamental domains can also be defined for more general group actions, but we will not need that in this paper.
The diamond’s crown or pavilion is drawn as a graph in the plane. We call the intersection of the graph with a fundamental domain a generating graph, since rotated and reflected images of this will fill out (i.e. generate) the whole graph.
It will follow from Theorem 3 that a generating graph for a diagram with D2n symmetry (n ≥ 3), can be used to generate a dihedrally symmetric diamond of any order ≥3. This phenomenon is illustrated with the generalized standard round brilliants and princesses in Figure 4.
Theorem 3 leads to the somewhat surprising conclusion that there is a 1-1 correspondence between the set of facet arrangements of diamonds with dihedral symmetry group D2n and D2m for any n, m ≥ 3.
2 FROM TWO TO THREE DIMENSIONS
A classical theorem of Steinitz [16, 17] states that convex 3D polyhedral are in 1−1 correspondence with triconnected planar graphs (also called Schlegel diagrams or c-nets.) A connected graph is said to be triconnected if deleting any set of ≤2 vertices leaves the graph connected. Ziegler [23] collects many proofs of Steinitz’s theorem, including one, the Maxwell-Cremona correspondence, which we make use of in Theorem 2. See the notes to Chapter 4 of Ziegler [23] as well as videos by Sheehy [13,14].
Thus one approach to enumerating diamond cuts is to enumerate triconnected planar graphs, and it is even the case that one could enumerate dihedrally symmetric Schlegel diagrams to recover dihedrally symmetric polyhdera [9]. However this would not take advantage of the special geometry of diamonds, that they decompose into crown, girdle, and pavilion, and would include many implausible diamond cuts.
Instead, we will consider diagrams of crowns and pavilions separately and determine when they can be embedded in the plane so that some assignment of z coordinates to each vertex gives a valid 3D geometry.
2.1 TRUSSES AND LIFTING DIAGRAMS
Let us consider a two dimensional picture of a diamond crown or pavilion wireframe (the 1-skeleton of the polytope). In order to convert this to a three dimensional wireframe, we need to assign a height (z-coordinate) to each vertex. The assignment of heights needs to create coplanar facets, while coplanarity of the vertices around the boundary is not necessary in order to form a diamond crown or pavilion.
In fact, as an illustration of this last point, in the 16 girdle facet model of the standard round brilliant, there are two types of vertices on the boundary of both crown and pavilion, which can be at different heights (Figure 5). The boundary vertices of a princess diamond, on the other hand, must all have the same height by symmetry.
Definition 1. We say a planar graph is liftable, if there is an assignment of heights to the vertices such that the lifted vertices in each bounded face are coplanar. Such an assignment will be called a lift.
We define a truss to be a lift of a 2D graph, and say it is convex if
- the outer boundary of the 2D graph is convex,
- the lifted facets meet in mountain rather than valley folds.
Let z = k be a plane such that k is less than the height of every lifted vertex. Form a polytope as the set of all points underneath the truss and above this plane. The above conditions ensure that this polytope is convex.
When enumerating diagrams, it will be most convenient if we only have to consider abstract graph types rather than particular embeddings, though we will need to keep track of the cycle of edges that forms the outer boundary. Note that every truss gives rise to an abstract planar graph with a specified cycle representing the outer edges.
Definition 2.
- A pair (G,C) consisting of a connected graph G and a specified cycle C ⊂ G will be called a circuited graph.
- All maps of circuited graphs to ℝ2 will be assumed to embed the specified cycle as a convex polygon, while the remaining vertices and edges will be mapped to the interior of this polygon.
- We say a circuited graph is liftable if it has a planar embedding which is liftable to a convex truss.
There is an analogue of Steinitz’s Theorem for trusses, but we need another definition to state it.
Definition 3. We say a circuited graph (G,C) is boundary triconnected if deleting any set of ≤ 2 vertices from G has the property that all connected components contain vertices from C.
Remark. The necessity of this formulation can be seen by considering the 8 vertex graph consisting of a square with each side bisected and 4 edges added to create a new square, rotated by 45 degrees, inside the first one. This is not triconnected and so does not correspond to a polytope, but it is liftable and could conceivably form the crown of a diamond.
Indeed, a top down view of such a graph appears in Figure 6 (Fig 22), a list of different diamond cuts in Diderot’s encyclopedia published in the late 1700s [6].
Before we state the main theorem, that boundary triconnected trusses are liftable, we take a slight detour to discuss the Tutte embedding.
2.2 TUTTE ON HOW TO DRAW A GRAPH
Let (G,C) be a circuited graph. Assign each internal edge e a positive weight se called its spring tension. Embed the outer cycle in the plane in any convex way and consider the vertices in this cycle to be immovable. Now think of the graph as being a network of nodes connected by springs and let it settle into equilibrium. In the equilibrium state, the sum of forces acting on each internal vertex will be zero. That is, if we scale each edge, thought of as a vector connecting its endpoints, by its spring tension, and then add all the edges outgoing from a single internal vertex, they should sum to zero as a vector. The positions of the internal vertices are easily calculated by solving the resulting system of equations.
If (G,C) is an abstract circuited graph, S is a set of spring tensions on the edges not in C, and φ: C →ℝ2 is a convex embedding of the boundary cycle, we denote the resulting image of the graph in the plane by Tutte(S,φ)(G,C), or just TutteS (G,C) if the boundary embedding is clear from context.
Theorem 1 (Tutte [19,20]). A circuited graph, (G,C), has a planar embedding and is boundary triconnected if and only if G has no interior bivalent vertices and Tutte(S,φ)(G,C) is an embedded graph in the plane, for any choice of positive spring tensions and convex boundary embedding.
We note that Tutte uses the term “3-linked with C” for what we call “boundary triconnectivity.”
One way that a graph can fail to be (boundary) triconnected is if it has a univalent vertex. When one puts a spring tension on the incident edge, the edge will shrink to zero, so Tutte(S,φ)(G,C), will fail to be embedded. Indeed the same reasoning applies if there is a cut vertex. The side of the cut vertex that fails to intersect C will contract to a point. Suppose you have two vertices whose deletion disconnects the graph into two components and one of the components does not intersect C at all. That means this entire component will shrink toward a line segment connecting the two points when positive spring tensions are applied. Therefore, Tutte(S,φ)(G,C) will again fail to be connected as long as the component was not itself linear (i.e. formed from a chain of bivalent vertices). So we conclude that the Tutte map will detect the failure of boundary triconnectivity except for the presence of interior bivalent vertices.
Theorem 2. A circuited graph is liftable iff it has a planar embedding and is boundary triconnected.
Moreover, if the circuited graph has symmetry group 𝒢, the truss can be constructed to have the same symmetry group.
Proof: First suppose that a circuited graph is liftable. Projecting a truss to the xy plane yields an embedding, so we need only show that a convex truss is boundary triconnected. Form the polytope as described after Definition 1. This polyhedron is triconnected. Now choose a pair of vertices in the truss, and suppose they disconnect it into two pieces. Since the whole polytope is triconnected, each piece must be connected to the edge of the truss for otherwise the polytope minus the two vertices would be disconnected. Hence the truss is boundary triconnected.
Next suppose that we have a boundary triconnected circuited graph with a planar embedding. Then by Theorem 1, the Tutte map yields an embedding where all the spring tensions are in equilibrium. Once the diagram is embedded, the standard proof of the Maxwell-Cremona correspondence goes through to lift to a truss. See Crapo&Whiteley [4,5].
Now suppose that a group 𝒢 acts on a boundary triconnected circuited graph (G,C) by automorphisms. Embed C as a regular polygon in the plane, and set all internal edge tensions equal to 1. Then the Tutte embedding will also have 𝒢 symmetry. We can choose a symmetric lift as follows. According to the Maxwell-Cremona correspondence (see [13,14]), lifts of a diagram are controlled by the spring tensions and a chosen facet normal. The spring tensions are used to construct a “reciprocal diagram,” while different choices of facet normal translate the reciprocal diagram around the plane. In order to get a symmetric lift, we center the reciprocal diagram on the origin.
The last paragraph of the proof implies that for symmetric graphs, the space of symmetric 3D realizations (with fixed (x,y) coordinates of the outer boundary and discounting vertical shifts) has the same number of dimensions as independent spring tensions plus the degrees of freedom in repositioning the reciprocal diagram while respecting the symmetry group. For D4 and higher, the reciprocal diagram must be centered on the origin, corresponding to the intersection of the reflection lines. For D2, the reciprocal diagram can be centered anywhere along a line through the origin parallel to the unique line of symmetry, adding one dimension to the parameter space. For the trivial group, there are two extra degrees of freedom. For any nontrivial rotational group Rn, there are no extra degrees of freedom. So parameter space has the same number of dimensions as interior edge orbits under the group action, possibly with the addition of 1 or 2 parameters for the groups D2 and D0 = R0 respectively. We have collected the dimensions of parameter spaces for three diamond faceting arrangements in Figure 7.
It is worth pointing out that Tutte’s method of drawing planar graphs is not the only one. A particularly powerful circle packing method is due to Mohar [10].
2.3 TRUSS RECOGNITION ALGORITHM
If we have a method to detect when the Tutte map is an embedding, then we can use the preceding section to create an algorithm for detecting trusses. One could simply check all pairs of edges of the Tutte map of a circuited graph for intersections, but we prefer to use a more combinatorial approach using ribbon graphs. It has the added benefit of detecting the faces of a planar graph, which is necessary information to implement the Maxwell-Cremona lifting algorithm for creating a 3D model.
A ribbon graph is defined to be an abstract graph with a cyclic order of incident edges at each vertex. A ribbon graph has a thickening to an oriented surface with boundary components, which is defined by putting an oriented disk at each vertex and gluing long thin rectangles along the edges using the cyclic order to indicate where they should be glued. (In fact, some authors only consider the thickened object to be a ribbon graph.)
One can read off the boundary components of the ribbon thickening by doing walks along the graph where, at each vertex, one leaves on the edge that comes next in the cyclic ordering after the edge one entered on. If you have a graph mapped (not necessarily embedded) to the plane
such that no edges emanate from a vertex in exactly the same direction, then there is an induced ribbon graph structure on the graph. One defines the cyclic order at each vertex to be induced by the plane’s orientation. Figure 8 shows the ribbon graph boundary components in a particular example. Many readers fail to notice that the two edges in the middle intersect, so be aware!
If a circuited graph is planar, then there is a bijection between boundary components and planar faces, so Euler’s formula v−e+ f = 2 must hold. (v,e,f being the number of vertices, edges, and faces, including the outer unbounded face, respectively.) Conversely, if v−e+ f = 2, the ribbon thickening is a sphere with holes, and gluing in disks to those holes gives an embedding of the graph in the sphere, where the specified cycle bounds a face. Designating that face as the unbounded face gives a planar embedding of the circuited graph. Hence the Tutte map must also be planar.
Summarizing, we get a truss recognition algorithm as follows. First check if the circuited graph is connected and that it has no bivalent vertices. If it passes these checks, consider a Tutte map of the graph. Check that it has no coincident vertices (within some tolerance), and that no edges emanate from a single vertex in the same direction (within some tolerance). If it passes these checks, thicken the graph, count the number of boundary components, and check if v−e + f = 2. If so, then it is a truss. Otherwise it is not.
3 ENUMERATION
Recall that any dihedrally symmetric diagram in the plane has a fundamental domain which is a sector of the plane bounded by a vertex at the diamond’s center, and two infinite rays, which we call walls and recall that the intersection of the planar graph with a fundamental domain is called the generating graph of the diagram. Note that the generating graph can have “half edges” which intersect either of the two boundary walls of a fundamental domain in right angles. This is illustrated in Figure 12. An edge emanating from vertex 1 meets the right wall, and in order to form a
valid edge upon reflection through the wall, must meet it at a right angle. Every diamond will have two generating graphs, one for the crown and one for the pavilion. Pavilion generating graphs will have a vertex at the top corner of a fundamental domain, corresponding to the culet, while crown generating graphs will not have a top corner vertex.
In order to systematically enumerate diamond crowns and pavilions with D2n-symmetry (n ≥ 3), we enumerate generating graphs. We distinguish types of graphs based on the combinatorics of the outer boundary of the generating graph.
The simplest situation is where there is a single exterior vertex in a fundamental domain, lying along one of the walls (see the princess crown and pavilion in Figure 3). We call diamonds with this property simple.
The next simplest situation is when there are two exterior vertices in a fundamental domain, one per wall. This occurs in the round brilliant crown and pavilion. We call diamonds with this property standard.
There could also be additional vertices along the bottom boundary of the generating graph, representing the outer edge of the diamond. This is evident in Figure 2 for the marquise diamond with symmetry group D4. Cushion diamond cuts can have D8 symmetry with such extra boundary
vertices (Figure 9).
We make the following additional assumption:
The b1 and b2 vertices are not bivalent.
Note that Diderot’s Fig 22 in our Figure 6 does give an example of a bivalent b1. So this is a nontrivial restriction.
It follows from the just stated assumption that in the simple and standard cases, the diagram must be triconnected, not merely boundary triconnected. Indeed the only way a simple or standard graph can be boundary triconnected but not triconnected is if b1 (or b2) connects to itself across a line of reflection. This will have the effect of cuting off a little triangular flap, as in the Diderot example, and will thus have a bivalent vertex.
For simplicity, we will restrict attention to simple and standard diamond cuts for the remainder of this paper. The techniques we present generalize fairly easily to the case of any number of vertices along the outer boundary of a fundamental domain. We suggest this to an interested researcher as a nice topic for further exploration.
For simple crowns and pavilions, we assume the outer vertex is on the right-hand wall, and label it b2. For standard crowns and pavilions, we label the outer vertices b1 and b2 for the left and right wall respectively. For a pavilion of either variety, the top corner of the chosen fundamental domain will have a vertex, which we label c.
Before we continue, we pause to prove that generating graphs are agnostic to symmetry order for n ≥ 3.
3.1 SYMMETRY ORDER
A generating graph can be used to generate graphs of any D2n-symmetry, n ≥ 3, by interpreting it in a sector of the correct angular width.
Theorem 3. Let G be a connected generating graph, and let Gn be the abstract circuited graph formed with D2n symmetry. Then Gn is planar and boundary triconnected for all n ≥ 3 iff G3 is planar and boundary triconnected.
Proof: Regarding planarity, note that Gn is planar iff the restriction to the sector is planar, a condition which does not depend on the sector’s angular width.
Next we show that a graph G3 is biconnected iff Gn is biconnected for any n ≥ 3. More specifically, we show that the existence of a cut vertex for any n is equivalent to the existence of one for n = 3.
Let us fix the following conventions for a connected graph G. Let c be a vertex of the graph. If G\{c}, considered as a topological space, is not connected, we say c is a cut vertex. The connected components of G\C where C is the set of cut vertices, are called the biconnected components. Note that according to this convention, the cut vertices themselves do not belong to biconnected components, and the biconnected components have open edges.
Because the biconnected components of G are disjoint, if σ ∈ Aut(G), g is a biconnected component, and (σ·g) ∩g ≠ ∅, then σ · g = g setwise. (*)
Now consider the circuited graph Gn. There must exist at least one biconnected component, g, which is adjacent to only one cut vertex, c, and which does not meet the graph’s exterior circuit. If g meets a wall away from c, then g overlaps with its reflection, so by (*), g is symmetric with respect to that wall. Hence c must also lie on the wall. If g meets any more walls, since it is symmetric in those walls, the vertex c will have a reflection that also meets g, contradicting that g meets at most one cut vertex. Thus g is contained in at most two adjacent fundamental domains. This implies that c will correspond to a cut vertex in any of the generated graphs Gk , k ≥ 3.
For triconnectivity we argue as follows. Suppose G is a biconnected graph. Then it can be decomposed into triconnected components [8], where a triconnected component is defined to be a subgraph which is triconnected and is not contained in a larger triconnected subgraph. Every edge belongs to a unique triconnected component, but vertices may belong to multiple components. We call the vertices of a component that belong to multiple components boundary vertices, and the rest of the component its interior.
Then Aut(G) acts on the sets of interiors of triconnected components. If σ ∈ Aut(G) and g is the interior of a triconnected component, then (σ · g) ∩ g ≠ ∅ implies that σ · g = g setwise as before.
Suppose one of the graphs Gn is not boundary triconnected. We can always find a triconnected component, g, with 2 boundary vertices whose interior does not meet the exterior circuit. We claim g is in at most two adjacent fundamental domains. Otherwise, suppose that g lies in three adjacent fundamental domains. Let r1 and r2 be reflections corresponding to the two interior walls separating these domains. Then I claim g is fixed setwise by both r1 and r2. If g doesn’t actually hit one of the two interior walls, then it is not connected, a contradiction. If it does hit a wall, there are two cases. It does so in the interior of g, then the point where it does is fixed by the associated reflection r, meaning that r fixes the entire component setwise. If g meets the wall in one of its two boundary vertices and nowhere else, then this vertex locally separates g, a contradiction.
But now notice that no matter how the boundary vertices are positioned, they can’t be invariant setwise under both r1 and r2.
Thus a nontrivial triconnected component will be present in G3 as well, and we conclude that the boundary triconnectivity of Gn is equivalent to that of G3.
3.2 FIRST STEPS
To illustrate how the enumeration algorithm works, let’s look at how to generate simple crowns and pavilions with small numbers of vertices.
Suppose there is one vertex in our fundamental domain aside from the boundary vertex b2. If that vertex lies at the top corner c, then it must connect to the boundary vertex by a single line. The generated graph represents a pyramid when lifted to 3D, which is the simplest possible pavilion. The generating graph is given at the top of the leftmost column of Figure 10, and three lifts of different symmetry order are depicted below it.
If the vertex lies along the right wall, it must connect to b2, but it must also connect to (a reflected copy of) itself, meaning it has an edge emanating to the left and meeting the left wall at a right angle. This leads to the second column of Figure 10, representing the simplest possible crown. Similarly, if the vertex is on the left wall, it must connect to itself and to b2, which yields the crowns in the fourth column. Finally, if the vertex lies in the middle, it needs to connect to itself both to the left and to the right, leading to the crowns in the third column. Switching to standard graphs leads to the diagrams in Figure 11.
In order to mechanize this process, we implement the Tutte embedding and truss recognition algorithm.
3.3 THE ALGORITHM
As we saw earlier, we are considering generating graphs that may or may not have a vertex at the top corner of the chosen fundamental domain (labeled c if it exists), and it may or may not have boundary vertices on either of the two walls of the fundamental domain, labeled b1 and b2.
The example in Figure 12 details how we encode generating graphs. The generating graph is pictured on the right. This is a simple crown, with only a b2 vertex. There are three types of vertices other than this boundary one. The two vertices labeled 1 and 2 lie on the left wall. We therefore call these “L” vertices. The vertex 3 is in the interior (or middle) of the fundamental domain, so we call it an “M” vertex. Finally, vertex 4 lies on the right-hand wall, so is called an “R” vertex.
Let nL,nM , and nR denote the number of vertices of each kind.
In Figure 12, the graph is encoded by the following data:
- The ordered triple (nL,nM ,nR) = (2,1,1).
- The edge connections of the vertices 1,...,4:
{1,3},{2,3},{3,4} - The edges that connect vertices with their reflections:
{1,1},{3,3,−1}
Here the−1 indicates that the edge is reflected through the left wall.
If the edge went through the right wall, we would use the notation
{3,3,+1}.
4. The list of vertices the corner attaches to, in this case {2,4}.
Similarly, if there are other boundary vertices we list the vertices those connect to as well. For example, referring to Figure 3, we have
Princess Crown | |
(nL,nM ,nR) | (1,1,1) |
(b1, b2, c) | (F,T,F) |
| edges | {{1,3},{1,2},{2,3},{2,2,−1}} |
| b2 connections | {2} |
Princess Pavilion | |
| (nL, nM , nR) | (4,0,1) |
| (b1, b2, c) | (F,T,T) |
| edges | {{1,2},{2,3},{3,4}} |
| b1 connections | {1,2,3,4} |
| b2 connections | {1} |
| Round Brilliant Crown | |
| (nL, nM , nR) | (1, 0, 1) |
| (b1, b2, c) | (T,T,F) |
| edges | {{1,2},{2,2}} |
| b1 connections | {1} |
| b2 connections | {1} |
| Round Brilliant Pavilion | |
| (nL, nM , nR) | (1, 0, 0) |
| (b1, b2, c) | (T,T,F) |
| edges | {} |
| b1 connections | {1} |
| b2 connections | {1} |
c connections | {1} |
Given such combinatorial data we can reconstruct the embedded generating graph as follows. First choose some n ≥ 3 and generate an abstract graph from the generating graph with symmetry group D2n. We have a specified outer cycle, so we can apply the Tutte embedding. Finally, we restrict to a fundamental domain to get an embedded generating graph.
Fix nL, nM , nR as well as the boundary vertex booleans b1, b2 , c which indicate whether the corresponding vertex exists or not. In order to find all generating graphs with these data, we list all possible feasible ways of abstractly connecting all the relevant vertices, then checking them all for planarity, triconnectivity and duplicates. We reduce the number of graphs that need to be searched by imposing some constraints that embedded graphs must satisfy:
- The subgraph spanned by each of the L or R vertices has to be a subgraph of a linear chain.
- The b2 vertex connects to at most one R vertex, while a b1 vertex will connect to at most one L vertex. A c vertex will connect to at most one vertex each of the L and R vertex sets.
So consider a graph TGraph(nL, nM , nR) on vertices of type L,M,R with edges in the following classes:
- A linear chain on the L vertices. (edge count: max(nL−1,0).)
- all edges connecting L vertices to M and R vertices. (edge count: nL(nM + nR).)
- all edges connecting M vertices to other M vertices and R vertices. (edge count:
- A linear chain on the R vertices. (edge count: max(nR−1,0).)
- All self edges on the L and R vertices. (edge count: nL + nR.)
- Two types of self edges (k,k,1) and (k,k,−1) on the M vertices. (edge count: 2nM .)
Next we consider graphs formed by all subsets of these edges, forming a list called abcBoolSets.We store each member of abcBoolSets as an array of booleans indicating whether a given edge is included or excluded from the graph.
We also define
- b1BoolSets encodes all possible sets of edges connecting b1 to the graph’s interior vertices. Its members are arrays of nL + nM + nR booleans, limited to at most one T in the first nL slots.
- b2BoolSets encodes all possible sets of edges connecting b2 to the graph’s interior vertices. Its members are arrays of nL + nM + nR booleans, limited to at most one T in the last nR slots.
- centerBoolSets encodes all possible sets of edges connecting cto the graph’s interior vertices. Its members are arrays of nL + nM + nR booleans, limited to at most one T in the first nL slots and one T in the last c.
- Booleans cb1 and cb2 indicate whether there are edges connecting c to bi.
Next we fix the size of elements of abcBoolSets, b1BoolSets, b2BoolSets and centerBoolSets to be j,k,l,m respectively (iterating over all possibilities). For each element of these, we form a concatenated string of booleans. This gives us a list boolGraphSet.
The next stage in the process is to remove duplicates caused by different labelings of the same graph. We consider the list of permutations XnL nM nR = SnL ×SnM ×SnR \{id}, i.e. the nontrivial permutations that respect the vertex types. Each permutation σ acts on a boolean array in g ∈ boolGraphSet by computing the action on T(nL,nM ,nR) and the edges coming from b1, b2 and c. In some cases, an edge in g when acted on by σ will not lie in T(nL,nM ,nR), which means this is not a valid relabeling. If the relabeled graph is valid, we call the result g.σ.
The algorithm for removing duplicates consists of going through every element of boolGraphSet, applying the permutations g ∈ XnL nM nR and removing valid results g.σ. In addition to removing duplicate graphs this algorithm will also remove graphs with nontrivial automorphisms. This is okay and actually desirable because any such generating graph will fail to either be connected or triconnected.
After applying the duplicate removing algorithm, we check each generating graph for connectivity using depth first search.
Next, relying on Theorem 3, each generating graph is generated into a graph with 3-fold symmetry. The Tutte map is then applied and the truss recognition algorithm is used to check if it is a truss. If not, it is discarded.
The remaining graphs are written to a file.
3.4 ALGORITHMIC COMPLEXITY
This is clearly an algorithm of exponential complexity in that it requires us to look at all subsets of edges of a certain master graph and iterate through all of these. We argue that, in fact, the number of D2n-symmetric simple and standard graphs is expected to be exponential in the number of vertices, implying that exponential complexity is unavoidable.
One reason to expect exponential complexity is Tutte’s beautiful result [21] that the set of rooted planar maps (which allow multi and self edges) with n edges is given by the unexpectedly simple formula
where a map is said to be rooted if one face is specified as the root. This at least hints at exponential complexity for our simple and standard graphs. More to the point, Tutte also considered rooted c-nets, which have the additional condition of triconnectivity. He proves that the number of rooted c-nets with n edges is asymptotically equal to
Although both of these numbers are in terms of edge count rather than vertex count, and refer to general graphs, rather than the special dihedrally symmetric ones we’ve been considering, the point of complexity
still stands.
Even though exponential complexity is unavoidable, there exist algorithms and software tools that work extremely well in practice. For example, Tutte’s methods actually give a generating function and an effective method of enumeration. See [1] for more analysis with generating functions. On the software side, Brinkman and McKay’s program plantri [3] efficiently enumerates some classes of planar graphs. See also the virtual environment CaGe [2]. The particular dihedrally symmetric case we restrict to in this paper does not seem to have been previously considered in the literature.
4 RESULTS AND TABLE
In this section we tabulate the results of the algorithm for simple or standard crowns and pavilions. We begin by listing the simplest examples as measured by the number of vertices in a fundamental domain. A generating graph needs to have at least one vertex on the boundary, and if the truss is not going to simply be a flat plane with no 3D geometry, there needs to be at least one other vertex. Hence we start with a fundamental domain containing 2 vertices.
4.1 Two vertices
There are four generating graphs with two vertices, each listed at the top of Figure 10. There is one simple pavilion and three simple crowns of the form (0,0,1), (0,1,0) and (1,0,0) respectively. The remaining rows of the diagram give diagrams with 4−,5−and 8-fold symmetry cf. Theorem 3.
4.2 Three vertices
Next we list generating graphs with 3 vertices, organized by which of the three corner vertices b1, b2, c are present.
Case 1: All three of b1, b2, c are filled. Then there is no other vertex in a fundamental domain, yielding a standard pavilion which is just a pyramid on a 2n-gon.
Case 2: Only b1, b2 are filled. This yields standard crowns with one non-corner vertex in a fundamental domain, so they must be of type (1,0,0),(0,1,0), or (0,0,1). There is one of each of these types, though
the last one is a rotation of the first one.
Case 3: Only b2 and c are filled, we get a simple pavilion with one extra non-corner vertex. There are 7 of these, three each of types (1,0,0), (0,1,0) and one of type (0,0,1).
Case 4: Only b2 is filled, we get a simple crown, with two extra non-corner vertices. There are 33 of these as summarized in this table:
Simple Crowns | ||||||
200 | 020 | 002 | 110 | 101 | 011 | total |
3 | 6 | 1 | 9 | 7 | 7 | 33 |
In Figures 13 and 14, the 4- and 5-fold lifts of the generating graphs of this section are listed.
4.3 FOUR VERTICES
The crown and pavilion graphs with 4 vertices are of the following forms:
- Simple crowns with three extra vertices:
Simple Crowns | ||||||||||
| 300 | 030 | 003 | 120 | 210 | 102 | 201 | 012 | 021 | 111 | total |
| 5 | 56 | 1 | 102 | 51 | 25 | 35 | 25 | 80 | 115 | 415 |
(Figure 15)
Simple pavilions with two extra vertices:
Simple Pavilions | ||||||
200 | 020 | 002 | 110 | 101 | 011 | total |
5 | 28 | 1 | 33 | 17 | 17 | 101 |
(Figure 16)
- Standard crowns with two extra vertices:
Standard Crowns | ||||||
200 | 020 | 002 | 110 | 101 | 011 | total |
3 | 16 | 3 | 19 | 13 | 19 | 73 |
See Figure 17 for 8-fold lifts of standard crowns with ≤ 4 vertices in a fundamental domain.
Standard pavilions with one extra vertex:
Standard Pavilions | |||
| 001 | 010 | 100 | total |
| 3 | 9 | 3 | 15 |
See Figure 18 for 8-fold lifts of standard pavilions with ≤ 4 vertices in a fundamental domain.
4.4 MASTER TABLE OF RESULTS
Figures 19 and 20 depict master tables of computational results. We set a limit of nL +nM +nR = 6 and list all triplets such that nL +nM +nR ≤ 6. For each triplet, we consider the four types of graphs determined by whether it is simple or standard and whether it is a crown or pavilion. Thus for example, there is 1 simple crown of type (0,0,4), 7 standard crowns of the same type, 1 simple pavilion, and 9 standard pavilions. Entries with a weather symbol were not computed at time of publishing. The symbols indicate difficulty of computation starting at ☼ which means less than 31.6 million graphs that need to be checked, then proceeding,⛅️, ☁️, ☁︎, ⛆, 🌧️, 🌨️, ⛈, with each one being 10 times the previous one, ending at 316 trillion graphs needing checking.
All entries were computed using C# code implementing the algorithm outlined in Section 3.2. Refactoring in C or C++ would provide a performance boost.
4.5 Odds and ends
There are a few patterns that stand out in the data. In order to discuss these, we define functions C0(a,b,c), P0(a,b,c), which count the number of simple crowns and pavilions of type (a,b,c), and C(a,b,c), P(a,b,c) which count the number of standard crowns and pavilions of type (a,b,c).
Proposition 4. The following equalities hold.
- C(a,b,c) = C(c,b,a) and P(a,b,c) = P(c,b,a).
- C0(0,0,n) = P0(0,0,n) = 1, C(0,0,n) = 2n−1, and P(0,0,n) = 2n+ 1
- C0(n,0,0) = C(n,0,0) = 2n−1. P0(n,0,0) = 2n+ 1. C(n,0,0) = 2n+ 1
- P0(1,0,n) = P0(0,1,n) and C0(1,0,n) = C0(0,1,n).
Proof: The first point follows because the vertices b1 and b2 can be interchanged. Here is a good point to note that the involution given by reflection of the diagram through the perpendicular bisector of b1,b2 acts on the sets counted by C(c,b,c) and P(c,b,c). Graphs fixed by this involution have a a higher order D2n+2 symmetry, while the other graphs are counted twice up to isomorphisms that allow boundary vertex permutation.
The fact that C0(0,0,n) = P0(0,0,n) = 1 can be seen as follows. There are n vertices lined up on the right hand wall. Each vertex can connect to the one above and below it as well as to itself across the left wall. All of the edges between consecutive vertices on the wall need to be filled in order for the graph to be connected. Moreover, since the vertex degrees need to be at least 3, the self-edges also need to be in place. Hence there is a unique such graph.
To see that C0(n,0,0) = 2n−1, let v0,...,vn be the list of vertices on the left wall, where the indices are in increasing order as you move down the wall. Given a generating graph on these, let vk be the maximal vertex that has a self-edge (which must cross the right hand wall). At least one such self edge is necessary or else the boundary vertex b2 would meet the diamond’s table, so the graph would not be triconnected. Once some vk has a self edge, all vertices with i < k must also have self edges for degree reasons. If k = n, then the graph is determined, each vk has a self-edge, each vi is connected to vi+1, and finally vn is connected to b2. Otherwise, consider the vertices with i > k. They must all connect to b2 for degree reasons and moreover the entire set of n vertices must be connected in a linear chain. Finally, the edge connecting b2 with vk may or may not be present, giving two options. In total we have 2(n−1)+1 = 2n−1 possible graphs.
The other equalities in point 3 are proved similarly.
The equalities in the last point come from expanding the L-vertex to an edge that crosses the left wall.
Proposition 5. The sequence C0(0,n,0) is equal to the number of c-nets with 3 outer vertices and n−3 inner vertices, which is OEIS sequence A285165. Our results match those of [1] within the calculated range.†
Sketch of proof: Given a C0(0,n,0) type generating graph, discard the bottom edge and introduce two new vertices that connect to all of the edges meeting the left and right walls, respectively. This gives us a planar graph with three outer vertices when we count the lower right boundary point of the fundamental domain.
We leave the reader with the following conjecture.
Conjecture 1. The number of simple crowns of type (1,0,n) is given by
C0(1,0,n − 1) = ⅓(4n3 + 6n2 + 8n + 3),
which is sequence A001845 in the OEIS.
Jim Conant is a Senior Research Mathematician at the Gemological Institute of America in Carlsbad, where he leads computational and geometric investigations into diamond cut quality, virtual facet patterns, and light-performance modeling. His work integrates advanced mathematics, computational geometry, and optical simulation to help develop the next generation of data-driven cut-grading and design tools used across the diamond industry.
