Properties of Delaunay Triangulations of Random Permutations

March 30, 2024

1117

Abstract

In this paper we study the properties of random permutations by applying Delaunay triangulations, using an approach that combines combinatorics and geometry. Our approach treats permutations as point clouds in 2D space, examining their properties within the framework of Delaunay triangulations, particularly focusing on configurations that exhibit geometric extremes. For several characteristics, such as the number of triangles and the area of the convex hull, we have proven minimum or maximum configurations using tools like the Euler characteristic. In addition, through numerical simulation, we have examined other characteristics and have proposed conjectures on how they evolve with increasing permutation length.

Keywords: Random Permutations, Delaunay Triangulations, Probability, Voronoi Diagram, Statistics.

Introduction

Random permutations are an area of study in combinatorics and probability that considers arrangements of random sequences of numbers. Analogous to a well shuffled deck of cards, a random permutation of length $n$ is a list of numbers that uniquely includes each integer from 1 to $n$ exactly once. Random permutations are fundamental to many domains, with applications in cryptography for the scrambling of data and statistical sampling for unbiased distributions. One can represent a given permutation as a set of $n$ points in the plane, where the index is the x-coordinate and the permuted value is the y-coordinate, thus transforming a permutation into a two-dimensional point cloud (see Definition 2.1 for details). This representation allows one to study random permutations using geometric properties of this representation. In particular, this geometric representation allows one to define statistics that are not immediately apparent otherwise. Geometric representations of permutations are useful in many problems such as modeling and scheduling memory space in computers¹,². A permutohedron is an $n-1$ dimensional figure generated from a permutation of length $n$ , with $n!$ vertices, and is an example of a link between geometry and permutations³. However, our work uses a very different transformation to map a permutation to two dimensions with $n$ vertices.

Delaunay triangulations provide a method for constructing a graph on a set of points on a plane which encodes geometric properties of the point arrangement. In particular, Delaunay triangulations are constructed such that no other points appear in the circumcircle of any triangle in the triangulation³,⁴. It also maximizes the minimum angles of the triangulation, thus avoiding overly skinny triangles and providing a more regular mesh. The Delaunay triangulation can also be viewed as the dual of the Voronoi diagram⁵,⁶, connecting points of close proximity. The circumcircle property in particular, can provide insight into the shape, structure, and relations between points since studying the resulting triangulation can provide clues about the uniformity of the resulting distribution of points⁷,⁸.

In this work, we introduce a new class of permutation statistics, based on the Delaunay triangulations of random permutations viewed as points in the plane. We introduce and analyze a number of such statistics, and in some cases, we are able to prove the value of these statistics as a function of $n$ . In other cases, we give conjectures backed by empirical computations.

The first part of this paper proves specific properties of the Delaunay triangulations that result from a random permutation. We can characterize extremal properties for several such statistics, including the maximum/minimum number of triangles appearing in the Delauney triangulation, the maximum/minimum number of points appearing on the convex hull and the maximum/minimum area of the convex hull, providing tight bounds for the values these statistics can take. Interestingly, some of these results rely heavily on the Euler characteristic, a topological invariant of triangulations. The second part of the work involves a data-driven analysis of the statistics that result from random permutations. We construct a dataset of samples from a set of permutations, and examine the dataset’s characteristics, using these trends to suggest properties inherent to the permutations, potentially advancing our understanding of random structures.

Definitions

Let $S_n$ denote the group of permutations on the set $[n]:=\{1,2,\ldots,n\}$ . We may represent any permutation as a set of points in $\mathbb{R}^2$ as follows:

Definition 2.1. Let $\sigma \in S_n$ , and let $[n] \times [n] \subset \mathbb{R}^2$ denote the set of points $(x, y)$ with $x, y \in [n]$ . Then we define $L(\sigma)$ to be the set of points $(x, \sigma(x))$ in $[n] \times [n]$ . $L$ defines a map from $S_n$ to the set of subsets of $[n] \times [n]$ , which we refer to as the $\mathbb{R}^2$ -embedding of $\sigma$ .

Definition 2.2. Let $P(S_n)$ denote the set of probability distributions on $S_n$ , i.e., functions $\mu: S_n \rightarrow \mathbb{R}{\geq 0}$ such that $\sum_{\sigma \in S_n} \mu(\sigma) = 1$ .⁹

Of particular interest is the uniform distribution $U \in P(S_n)$ , which assigns each $\sigma \in S_n$ mass $\frac{1}{n!}$ .

Definition 2.3. Let $X: S_n \rightarrow \mathbb{R}$ be a function, which we refer to as a permutation statistic¹⁰. Let $\mu \in P(S_n)$ . Then we define the expectation of the statistic $X$ with respect to $\mu$ as follows:

(1) $\begin{equation*}E_{\mu}(X) = \sum_{\sigma \in S_n} X(\sigma) \mu(\sigma) \end{equation*}$

In this paper, we initiate the study statistical properties of a class of functions on $S_n$ , which we refer to as permutation statistics. To properly define these functions, we must first define Voronoi diagrams and their dual Delaunay triangulation:

Definition 2.4. Let $S={s_i}_{i=1}^n$ be a set of points in $\mathbb{R}^2$ . We may partition $\mathbb{R}^2$ into sets $U_i$ defined by the following relation¹¹:

(2) $U_i := {x \in \mathbb{R}^2 \;|\; |x - s_i|^2 \leq |x - s_j|^2, \; \forall j \in [n]}$

We call the partition ${U_i}_{i=1}^n$ the Voronoi diagram on the sites $S$ , which we denote by $V(S)$ . We refer to the class of Voronoi diagrams with $n$ sites in $\mathbb{R}^2$ as $V_n$ .
Every Voronoi diagram in $\mathbb{R}^2$ has an associated cell complex, obtained by taking the combinatorial dual to the partition defining the Voronoi diagram:

Definition 2.5 Let $V(S)$ be a Voronoi diagram with $n$ sites. Let $G(S)$ be the metric graph with vertex set given by $S$ and an edge $e_{ij}$ between $s_i$ and $s_j$ if $U_i$ and $U_j$ are adjacent. We refer to $G(S)$ as the Delaunay triangulation⁴ of $V(S)$ . We refer to the set of Delaunay triangulations with $n$ vertices as $\hat{V}n$ .

Any Delaunay triangulation is (trivially) a planar graph. Outside of special, degenerate cases, the correspondence between a Voronoi diagram and its Delaunay triangulation is unique.

In this paper, we will introduce and study several functions of the form $g$ . We will mainly be interested in the statistical properties of such functions on $S_n$ for varying values of $n$ . Several conjectures and open questions will be posed.

Extremal results for $\mathbb{R}^2$ -embeddings of permutations

In this section, we establish some extremal properties of Delaunay triangulations obtained from $\mathbb{R}^2$ -embeddings of permutations. This gives tight bounds for the values these statistics can take. We first establish tight bounds for the number of triangles appearing in Delaunay triangulations of $\mathbb{R}^2$ -embeddings of permutations using Euler characteristic arguments. We then establish tight bounds for the area of the convex hull of Delaunay triangulations of $\mathbb{R}^2$ -embeddings.

Minimum and maximum number of triangles

Definition 3.1. Let $G$ be a planar graph. Then a face of $G$ is a connected, two-dimensional subset of $\mathbb{R}^2$ enclosed by a cycle of $G$ .

We now introduce an important topological tool we will use to study Delaunay triangulation:

Definition 3.2. Let $G$ be a graph. The Euler characteristic¹² of $G$ , denoted $\chi(G)$ , is equal to $V-E+F$ where $V$ is the number of vertices in the graph, $E$ is the number of edges in the graph, and $F$ is the number of faces in the graph. In a plane, this value is always $2$ , so in a Delaunay triangulation, the value of $V-E-F=2$ .

Definition 3.3. Let $V$ be a set of points in $\mathbb{R}^d$ . Then the convex hull¹³ of $V$ is the minimal convex set $C_V$ such that $(V \subset C_V )$ , i.e., if there exists a convex set $C'$ such that $V \subseteq C_{V'}^{\prime} \subseteq C_V$ then $C'_V = C_V$ .

Definition 3.4. Let $C_L(\sigma)$ be the convex hull of $L(\sigma)$ for a permutation $\sigma$ . Let $||C_L(\sigma)||$ be the number of points on the boundary of the convex hull. Then the minimum number of points in the convex hull is $( \min_{\sigma \in S_n} ||C_L(\sigma)|| )$ . The maximum number of points in the convex hull is $( \max_{\sigma \in S_n} ||C_L(\sigma)|| )$ .

Definition 3.5. Min/max number of triangles

Let $m$ represent the number of triangles for a value $n$ , denoted as the number of triangles in $\triangle(G(L(\sigma)))$ .

The minimum number of triangles, denoted as $\min(m)$ , is achieved when $\triangle(G(L(\sigma)))$ is minimized for the value of $\sigma$ .

Similarly, the maximum number of triangles, denoted as $\max(m)$ , is achieved when $\triangle(G(L(\sigma)))$ is maximized for the value of $\sigma$ .

We can maximize the number of points on the convex hull to minimize the number of triangles in a permutation using the Euler characteristic.

Theorem 3.1. Let $D$ be a diagram in set $\hat{V}n$ with $n$ points such that the vertices of $D$ are the points in a random permutation graph $\sigma$ , there are two cases:

Case 1: If $n$ is odd, let $G(L(\sigma))$ be the random permutation graph that has a point on coordinate $(1,1)$ , $(n-1)/2$ points such that the $m$ th of these new points have coordinates $(2m,2m + 1)$ , and another $(n-1)/2$ points such that the $m$ th of these new points to be added will have coordinates $(2m + 1,2m)$ . An example of this case is shown in Figure 1.

Fig 1: Permutation grid given when $n = 5$ for case 1 that minimizes the number of triangles.

Case 2: If $n$ is even, we define $G(L(\sigma))$ as the result when we create the structure for $\sigma$ when there are $n-1$ elements, then add an element to the top right of the grid of size $n$ . For both cases, the minimum possible number of triangles in $D$ is $n-2$ .

To prove this theorem, we first prove $\sigma$ is the graph with the minimum number of triangles in $\hat{V}n$ .

To maximize the number of points on the convex hull of $G(L(\sigma))$ , we want to find if it is possible for every point on $G(L(\sigma))$ to be on the convex hull. First, when $n$ is odd, $G(L(\sigma))$ uses every odd $y$ coordinate up to $n$ exactly once, as the $(2x,2x + 1)$ coordinates have every odd $y$ coordinate from 3 to $2\left(\frac{{x-1}}{2}\right)+1=x$ , while the coordinate $(1,1)$ means $y = 1$ is used once. The $(2x,2x+1)$ coordinates include every positive even $x$ coordinate less than $n$ . Thus, every $x$ coordinate is used exactly once. Every odd $y$ coordinate less than or equal to $n$ is used exactly once, as the $(2x,2x+1)$ points include every $y$ value from $3$ to $n$ , and the point on the bottom left has $y$ coordinate $1$ . Similarly, every even $y$ coordinate less than $n$ appears exactly once since the $(2x+1,2x)$ coordinates include every even $y$ coordinate exactly once. Thus, $G(L(\sigma))$ has a point on each possible $x$ value, and a point on each possible $y$ value, so the pattern of points forms a valid permutation.

The $(2x,2x+1)$ points form a line with slope $1$ , while the $(2x+1,2x)$ points also form a line with slope $1$ . Thus, since the first and last points of these sets of points are separated by a slope of $1$ , the set of points in the permutation excluding $(1,1)$ forms a rectangle. This rectangle will be the convex hull of the set of points in the permutation not including $(1,1)$ , and every one of those points will be on the convex hull. Adding $(1,1)$ to this set will result in $(1,1)$ being on the convex hull, since $(1,1)$ is outside the rectangle and since $(1,1)$ is between the parallel lines of slope $1$ , every other point will still be on the convex hull. Thus, this arrangement will always have every point on the convex hull.

If $n$ is even, when we create the structure for Case 1 using $n-1$ elements, we add an element to the top right of the grid of size $n$ . This point will be on the convex hull since it is outside the rectangle and away from the bottom left point. Similarly, this new point is between the parallel lines of the rectangle, meaning every point on the previous hull is still on that hull. Thus, this structure forms a convex hull of every point.

Consequently, there is always a way for the convex hull to contain every point on the grid. Since the number of triangles in a triangulation is $2n-h-2$ triangles where $h$ is the number of points on the convex hull, to minimize this number, we maximize $h$ , which results in $h = n$ . Thus, the minimum number of triangles is $2n-n-2 = n-2$ triangles.

We now show there exists a permutation where three points of the permutation are on the convex hull, and the maximum number of triangles in a permutation in $S$ is $2n-5$ .

Theorem 3.2. For $n > 2$ , there is at least one permutation of $S$ such that exactly three points of the permutation are on the convex hull, and the maximum number of triangles in a random permutation is $2n-5$ .

Let $\sigma$ be a permutation in $S$ such that the first $n-2$ terms of $S$ do not change position. Thus, the coordinates of the first $n-2$ points of $S$ are the first $n-2$ lattice points with positive coordinates on the line $y = x$ . Let the other two coordinates of $\sigma$ be $(n,n-1)$ , and $(n-1,n)$ . This is one of the permutations that can cause the number of triangles in the permutation to equal $n-2$ . Figure 2 shows the permutation grid given when $n=5$ .

Fig 2: Permutation grid given when $( n=5 )$

Proof: To prove this theorem, let $(1,1)$ , $(n,n -1)$ , and $(n-1,n)$ be the three vertices of $\triangle ABC$ . We want to prove that $\triangle ABC$ is the convex hull of the permutation grid, so we need to determine every point in the permutation not on $\triangle ABC$ is inside $\triangle ABC$ . For any point $(m,m)$ such that $m$ is an integer and $1 < m < n -1$ , we can use ray casting to determine if this point is inside $\triangle ABC$ . In this method, we draw a line through $(m, m)$ , and if this line intersects the triangle an odd number of times on one side of the line, and an odd number of times on the other side of the line, the point is inside the triangle. We apply this method to the vertical line $x = m$ . The side of the triangle between $(1,1)$ and $(n,n - 1)$ has equation

$y=\frac{n-2}{n-1}\cdot x+\frac{1}{n-1}.$

This line will intersect equation $x = m$ since the endpoints of the triangle edge have one point on each side of line $x = m$ . Thus, $x = m$ intersects the side at

$y=\frac{n-2}{n-1}\cdot m+\frac{1}{n-1}=\frac{n\cdot m-2\cdot m+1}{n-1}.$

This value is lower than $(m,m)$ since $n \cdot m - 2 \cdot m + 1 < n \cdot m - m = m(n - 1)$ ,

$\frac{n\cdot m-2\cdot m+1}{n-1} < m\frac{n-1}{n-1}=m.$

The line connecting $(1,1)$ and $(n - 1,n)$ has equation

$y=\frac{n-1}{n-2} x-\frac{1}{n-2}.$

This side of the triangle will intersect $(m,m)$ since the endpoints of the side have one point with $x$ lower than $m$ , and one point with $x$ higher than $m$ . Thus, the side intersects line $x = m$ at

$y=\frac{n-1}{n-2} x-\frac{1}{n-2}=\frac{m\cdot n-n-1}{n-2}.$

This point is higher than $(m,m)$ since $m \cdot n - n - 1 > m \cdot n - 2 \cdot n$ , so

$\frac{m\cdot n-n-1}{n-2} > \frac{m\cdot n-2\cdot n}{n-2}=m.$

Line $x = m$ does not intersect the edge consisting of $(n-1,n)$ and $(n,n-1)$ since both vertices of this edge are to the right of the line $x = m$ . Thus, the vertical line from $(m,m)$ intersects exactly one edge above $(m,m)$ , and exactly one edge below $(m,m)$ . Thus, $(m,m)$ is contained in $\triangle ABC$ , so $\triangle ABC$ is the convex hull. Since a convex hull must consist of over $2$ points, this triangle achieves the minimum number of points on the convex hull, and it is always possible for the convex hull to consist of $3$ points.

We use Euler’s formula again, which is every triangulation has $2n-h-2$ triangles, where there are $n$ points, and $h$ points on the convex hull. Since the minimum number of points on the convex hull is $3$ , and this value is always attainable for $n > 2$ , we can maximize $2n-h-2$ by minimizing $h$ . We assign $h = 3$ to Euler’s formula to find the maximum number of triangles is $2n-3-2 = 2n-5$ .

The maximum area of the convex hull

Definition 3.6. Maximum area of the convex hull.
The maximum area of the convex hull over the set of graphs $S$ is $\max_{\sigma \in S} \left{ \text{(area}_{\text{convex}} (\sigma) \right}$ .

Theorem 3.3. The maximum area of the area of a random permutation graph is $n^2-4n+5$ .

Proof: The proof relies on the following lemma:

Lemma 3.10. For a permutation of size $n$ , the convex hull of the permutation contains exactly one point where $x = 1$ , one point where $x = n - 1$ , one point where $y = 1$ , and one point where $y = n - 1$ .

Proof of Lemma: Each edge of the grid has exactly one point on it due to random permutations having each element appear exactly once. Let the element on one of the edges of a grid be element $A$ . Let the set of points on the grid other than $A$ be set $B$ . The convex hull of set $B$ cannot include element $A$ , since all elements $B$ are on the same side of $A$ . Thus, $A$ is on the convex hull of the set of elements $B + A$ . We can repeat this on each side of the grid to find every side of the grid has a point on the convex hull of the random permutation.

Now we prove the maximum area of a random permutation graph is $n^2-4n+5$ . Let the permutation matrix with maximum area be named permutation $\sigma$ , such that $\sigma$ has size $n$ . $\sigma$ has either $0$ corners with a vertex, $1$ corner with a vertex, or $2$ corners with a vertex. We will now find the maximum convex hull area for each of these scenarios. Figure 3 shows the examples of $0$ , $1$ , and $2$ corners with a vertex.

Case 1: Zero corner with a vertex

Let square $S$ be the square with vertices $(1,1)$ , $(1,n)$ , $(n,1)$ , and $(n,n)$ . For a corner $A$ of square $S$ , let the two points in $\sigma$ on the sides of $S$ adjacent to $A$ on the side be $B$ , and $C$ such that $AB = x$ , and $BC = y$ . Let the area of the shape consisting of vertices $A$ , $B$ , $C$ , and the vertices on the portion of the convex hull between $B$ and $C$ be a value $d$ . The minimum possible value of $d-(x+y)/2$ is $-1/2$ , which occurs when $d=(x+y-1)/2$ and either $x$ or $y$ is $1$ .

If $x$ and $y$ are not $1$ , the minimum possible value of $d$ would be $(x+y)/2$ if a point on the convex hull is on the diagonal of the unit grid from $A$ . The area of the convex hull of $\sigma$ is the area of $A$ minus the values of $d$ for every corner of the grid. Since the minimal value of $d-(x+y)/2$ is $-1/2$ , the sum of the different $x + y$ values across the shapes of $d$ is the perimeter of the grid, which is $4(n-1)$ . Since the sum of all values of $d-(x+y)/2$ across all corners is $4\cdot(-1/2)=-2$ , and the sum of all $(x+y)/2$ across all corners is $4(n-1)/2=2n-2$ , then the minimum sum of all values $d$ is $2n - 2 - 2 = 2n - 4$ . Since the minimum possible value of the sum of the values of $d$ is $2n - 4$ , and the area of the convex hull of $\sigma$ is $(n-1)^2$ subtracted by the sum of all values of $d$ , the maximum area of the convex hull is $(n-1)^2-(2n-4)=n^2-4n+5$ . An example of the grid for minimum possible area for case 2 is shown in Figure 3, which shows the minimum area of case 1 when $n=7$ .

Case 2: One corner with a vertex

Let the square have vertices $ABCD$ such that the corner of the grid in $\sigma$ is $A$ . Let the vertices of $\sigma$ on the other edges be $X$ , which is on $BC$ , and $Y$ , which is on $CD$ . We want to minimize the area of the shape consisting of $A, B, X$ , and the vertices on the convex hull between $A$ and $X$ , the shape consisting of $X, C, Y$ , and the points on the convex hull between $X$ and $Y$ , and the shape consisting of $A, D, Y$ , and the points on the convex hull between $A$ and $Y$ . The way to minimize an area is to have a point that is diagonal from the corner with distance $1$ for both $x$ and $y$ coordinates. If one of the side lengths of the sides is $1$ , the area is the average of the side lengths minus $1/2$ , while otherwise, the area is the average of the side lengths. Since there will always be at least one grid with both side lengths not equal $1$ , the minimum area outside the convex hull is $4n - 5$ , resulting in the area of the convex hull being $(n-1)^2-(2n-3)=n^2-4n+4$ , so this case is suboptimal. An example of the grid for the minimum possible area for Case 2 is shown in Figure 4, which shows the minimum area of Case 2 when $n=7$ .

Case 3: Two corners with vertex

In this case, the two corners must be opposite corners since no side can contain two points simultaneously. We want to minimize the area consisting of the two corners, along with the concave portion of the convex hull between those two corners. The minimum area is achieved when there is a point on the permutation one point from the diagonal of a corner not on the permutation, resulting in an area of $n$ . An example of such a permutation is shown in Figure 5, which shows the minimum area for Case 3 when $n=7$ . Thus, the total area is $(n-1)^2-(2n-2)=n^2-4n+3$ , which is sub-optimal. Thus, the optimal method is Case 1, with an area of $n^2-4n+5$ .

Experimental (conjectures): Minimum maximum edge length, minimum maximum triangle area

Minimum maximum edge length

Definition 4.1. Minimum maximum edge length

Let the minimum of the maximum edge length for the set of graphs $( S )$ be defined as $\min_{\sigma \in S} \left(\max\left(\text{length}(\sigma)\right)\right)$ .

Conjecture 4.1. For every value $n > 4$ , the minimum maximum edge length in $S$ will equal $\sqrt{10}$ . We ran a simulation through all values $n$ between $5$ and $10$ inclusive, and found all of these values have a minimum maximum edge length of $\sqrt{10}$ . The graph that yields this value for $n = 10$ is shown in Figure 6 below.

Fig 6: The minimum maximum edge length for $n=10$ plotted by Python Matplotlib

Consider this series of rectangles aligned diagonally such that the minimum maximum edge length is always $\sqrt{10}$ . Let $m$ represent the number of triangles. Increasing $n$ by $2$ increases $m$ by 2, maintaining the minimum maximum edge length. As we can see, we can indefinitely add rectangles to the series of rectangles stacked in the diagonal direction, while keeping the same minimum maximum edge length of $\sqrt{10}$ . Since adding each rectangle increases $n$ by 2, and this shape works for $n = 6$ , we find every even number $n > 4$ could form a shape with a minimum maximum edge length of $\sqrt{10}$ . We can also remove a point from one of the corners of the grid to form a shape with a minimum maximum edge length of $\sqrt{10}$ with a value $n$ that is $1$ less than the original shape. Thus, it is possible to form a shape with a minimum maximum edge length of $\sqrt{10}$ for all integers $n$ such that $n > 4$ , and $n$ is odd. Thus, every integer $n > 4$ has a shape that has a minimum maximum edge length of $\sqrt{10}$ . However, we were not able to disprove the possibility of a shape existing with a minimum maximum edge length less than $\sqrt{10}$ for values $n > 10$ .

Minimum maximum triangle area

Definition 4.2. The minimum maximum triangle area for a number $n$ is the value found through finding the maximum triangle area of every Delaunay triangulation of random permutations and taking the minimum of these values.

Let $\Delta(G(L\sigma))$ denote the set of triangles in the graph $G(L\sigma)$ for each $T$ in $\Delta(G(L\sigma))$ , let $||T||$ be the area of the triangle. Then the minimum maximum triangle area for $S_n$ is: $\min_{\sigma \in S_n} \left( \max_{T \in \Delta(G(L(\sigma)))} | |T| | \right)$

Conjecture 4.2. We predict the minimum maximum area for a number $n$ will be $1.5$ for any value $n > 2$ . This prediction is based on a program we ran that solves the minimum maximum area for all values $n$ between $3$ and $10$ , where we found the value is always $1.5$ . The graph that yields $1.5$ for $n = 10$ is shown in Figure 7.

Fig 7: The minimum maximum area for $n=10$ plotted by Python Matplotlib

We can apply the Gauss’s area formula on every triangle involving two points on the $y = x$ line, given points $(x,x)$ , $(x + 1,x + 1)$ , and $(n-2,n-1)$ . We only solve the area of the cases involving one of the two points on the top right since these cases will have the same area as if we were to use the other point. The area is:

$\frac{{((x+1)x-(x+1)x+(x+1)(n-1)-(x+1)(n-2)+(n-2)x-(n-1)x)}}{2} = \frac{1}{2}$

As we can see, we can extend this graph by adding points along the diagonal line, allowing us to create this shape for all values $n > 10$ . Furthermore, this shape always has a minimum maximum area of $1.5$ since the area of the large triangle at the top right is $1.5$ , while the area of every other triangle is $0.5$ . However, we were neither able to prove nor confirm there exists another shape with $n > 10$ that has a minimum maximum area of $1.5$ .

Experimental Study

We gathered statistics regarding the graphs of the random permutations using the SciPy Python library. We generated 100,000 permutations of each size from $n = 3$ to $n = 20$ , and found the average of different permutation properties. We noted some of the more interesting properties, and formed conjectures regarding these properties. Some interesting statistics to analyze in the future are the following permutation statistics:

Average Triangle Area:
Average triangle area is defined as

$\frac{1}{{T(\sigma)}} \sum_{i=1}^{T(\sigma)} A_i$

where the function $T(\sigma)$ equals the number of triangles in $\sigma$ , and set $A$ is the set of the area of each triangle in $\sigma$ .

Fig 8: Average triangle area as a function of permutation length. Linear regression shown in red.

The average area of the convex hull should increase quadratically since as n increases, the convex hull should more closely resemble the grid’s perimeter. In addition, the number of triangles in the triangulation should increase linearly since the number of triangles in a random permutation must be between $n-2$ and $2n-5$ , both of which scale linearly. Since the average triangle area of a permutation is the area of its convex hull divided by its number of triangles, the average triangle area of a permutation should converge to scaling linearly. Thus, we conjecture the average triangle area of a permutation will converge to scaling linearly as illustrated in Figure 8.

Average Edge Length:
Let average edge length be defined as

$\frac{1}{{E(\sigma)}} \sum_{i=1}^{E(\sigma)} L_i$

where $E(\sigma)$ represents the number of edges in $\sigma$ , while the set $L_i$ is the set of the edge length of every edge in $\sigma$ .

Fig 9: Average edge length as a function of permutation length. Linear regression shown in red.

Average edge length is the average length of all edges in a random permutation. As $n$ increases, the shapes of the different triangles should have similar distributions, so the average triangle area should converge to the square of the average edge length. Since average triangle area converges to a near linear function, average edge length should converge to being near proportional to $\sqrt{n}$ . Thus, we conjecture the average edge length of a random permutation should converge to being proportional to $\sqrt{n}$ .

Minimum Edge Length:
Let minimum edge length be defined as $\min_{1 \leq i \leq E(\sigma)} L_i$ , where $E(\sigma)$ represents the number of edges in $\sigma$ and $L_i$ is the length of the $i$ th edge.

Fig 10: Minimum edge length as a function of permutation length. Linear regression shown in red.

The function of average triangle area for the random permutation with respect to permutation size is simulated in Figure 10. For an edge length of length $x$ , there is a constant number of relative positions between two points that could give that edge length. For each point in the permutation, as $n$ increases, the chance of a point forming a line of length $x$ with a given other point is close to this constant value of relative positions between two points divided by $n^2$ , since there are approximately $n^2$ possible points a point could be. There are approximately $n$ points that a given point can possibly form an edge length of $x$ with, so the chance of a given point forming an edge length of length $x$ is proportional to $\frac{1}{x}$ . Since there are $n$ initial points to choose from, there will thus be a constant chance of an edge length of length $x$ appearing as $n$ increases. Thus, as $n$ increases, the expected minimum edge length of length $x$ should be closer to constant since any edge length’s chance of appearing will always remain similar. Thus, we conjecture the average minimum edge length of a permutation will converge to a constant.

Conclusion

In this paper, we introduce a new class of permutation statistics. These are defined through geometrically representing permutations as a set of points in the plane and studying their resulting Delaunay triangulations. Our analysis led to the development of several proofs regarding the statistics of resulting permutations. The use of topological techniques, such as the Euler characteristic, was a key part of our analysis. Overall, the study contributes to the fields of combinatorics and geometry, offering a new perspective on permutation analysis. Through numerical simulation, we computed and analyzed the trends of the resulting permutations, finding conjectures for how the resulting triangulations scale with larger permutations.

We believe our geometric analysis of permutations can find practical applications in areas such as statistical sampling, and Monte Carlo simulations, problems that use permutations and are often spatial in nature. While our work has made contributions, there are also some limitations, pointing the direction toward future work. Many of the conjectures based on our data driver analysis we believe could be rigorously proven. We are also interested in refining our simulation methods, for example using a Monte Carlo approach, rather than uniform sampling, to better determine the triangulation geometric extrema for larger permutations. Overall, our findings offer insights in combinatorics through geometry, enhancing the understanding into the spatial structures can be hidden in random permutations.

Acknowledgements

We would like to thank Brendan Mallery for his mentorship and assistance in the preparation of this manuscript.

Shimon Even, Amir Pnueli, and Abraham Lempel. Permutation graphs and transitive graphs. Journal of the ACM (JACM), 19(3):400–410, 1972. [↩]
Amir Pnueli, Abraham Lempel, and Shimon Even. Transitive orientation of graphs and identification of permutation graphs. Canadian Journal of Mathematics, 23(1):160–175, 1971. [↩]
Alexander Postnikov. Permutohedra, associahedra, and beyond. International Mathematics Research Notices, 2009(6):1026-1106, 2009 [↩] [↩]
Steven Fortune. Voronoi diagrams and Delaunay triangulations. Handbook of discrete and computational geometry, 705-721, 2017 [↩] [↩]
Franz Aurenhammer. Voronoi diagrams—a survey of a fundamental geometric data structure. ACM Computing Surveys (CSUR), 23(3):345-405, 1991 [↩]
Adam Dobrin. A review of properties and variations of Voronoi diagrams. Whitman College, 10(1.453):9156, 2005 [↩]
Min Deng, Qiliang Liu, Tao Cheng and Yan Shi. An adaptive spatial clustering algorithm based on Delaunay triangulation. Computers, Environment and Urban Systems, 35(4): 320-332, 2011 [↩]
Jongwon Kim and Jeongho Cho. Delaunay triangulation-based spatial clustering technique for enhanced adjacent boundary detection and segmentation of LiDAR 3D point clouds. Sensors, 19(18):3926, 2019 [↩]
Jaynes, Edwin T. Probability theory: the logic of science. St. Louis, MO: Washington University, 1996. [↩]
Dokos T, Dwyer T, Johnson BP, Sagan BE, Selsor K. Permutation patterns and statistics. Discrete Mathematics. 2012 Sep 28;312(18):2760-75. [↩]
Franz Aurenhammer and Rolf Klein. Voronoi diagrams. Handbook of computational geometry, 5(10):201–290, 2000. [↩]
Eckmann, Beno. “The Euler characteristic—a few highlights in its long history.” Mathematical Survey Lectures 1943–2004 (2006): 177-188. [↩]
, Joseph. Computational geometry in C. Cambridge university press, 1998. [↩]

Check out other related articles on NHSJS

2 COMMENTS

Buy Private Proxies April 1, 2024 At 04:45

It’s a shame you don’t have a donate button! I’d most certainly donate to this excellent blog! I guess for now i’ll settle for book-marking and adding your RSS feed to my Google account. I look forward to brand new updates and will share this website with my Facebook group. Talk soon!

- Kai Lum April 1, 2024 At 12:53
  
  Thank you for your support. I’m glad you liked it.

Properties of Delaunay Triangulations of Random Permutations

Abstract

Introduction

Definitions