# The Geometric Viewpoint

geometric and topological excursions by and for undergraduates

• Category Archives Uncategorized
• ## Tessellations of the Hyperbolic Plane and M.C. Escher

(this post is by Allyson Redhunt)

“For me it remains an open question whether [this work] pertains to the realm of mathematics or to that of art.” -M. C. Escher

Figure 1. M.C. Escher [7].

Escher’s beginnings
M. C. Escher (1898-1972) (Figure 1) is known for his mind-boggling artwork that challenges our sense of space. Although many of his works are artistic renditions of deep mathematical ideas, he had no formal training in mathematics. In fact, he was a poor student in high school–struggling to earn a diploma. In his post-secondary education, he was trained at the School of Architecture and Decorative Arts in Haarlem. This is where he developed his fascination with structure.
Although he began as an architecture student, he was soon switched to a decorative arts path. During his schooling, he did some traveling and was exposed to Moorish motifs. These works of design are created from mathematically careful patterns. From their influence, Escher’s art branched into tessellations of the plane. He was inspired by the idea of “approaches to infinity” and began by playing with flat surfaces and spheres.

Figure 3. Coxeter’s tessellation [2].

Escher’s ideas about structure, pattern, and infinity were suddenly enhanced when he came across the work of geometer H. S. M. Coxeter (1907-2003). Coxeter and Escher struck up a correspondence when Coxeter hoped to use Escher’s unique depictions of symmetry in a presentation for the Royal Society of Canada. Coxeter sent Escher a copy of the talk, which included an illustration depicting a tessellation of the hyperbolic plane (Figure 3) [2]. This image sparked a new area of Escher’s exploration of infinity [6]. To fully understand the beauty of his works, it is helpful to have a basic understanding of hyperbolic geometry.

A crash course in hyperbolic geometry
So what is hyperbolic space? Grade school mathematics is taught using Euclidean geometry. This assumes Euclid’s axioms, which he intended to be the basis of all geometry. However, one of them was a great source of debate between mathematicians. The “Parallel Postulate,” which states that if one straight line crosses two other straight lines to make both angles on one side less than 90˚, then the two lines meet. Proving that triangles have 180˚ angle sums is an application of this postulate [4].
However, the Parallel Postulate need not hold true in all cases, such as on the surface of a sphere. Proving that the postulate need not hold led to the discovery of an important “non-Euclidean” geometry called hyperbolic geometry. Although it at first seems unnatural to think about parallel lines performing in “new” ways, hyperbolic surfaces can be found in nature. Two common examples are sea slugs (Figure 4) and lettuce (Figure 5). The wavy structure is the tip-off that their surfaces exhibit hyperbolic geometry. This is because, while a Euclidean surface has curvature equal to zero everywhere, a hyperbolic surface has constant negative curvature (for comparison, a sphere has constant positive curvature).

Figure 4. Close up of a colorful nudibranch [8]. Figure 5. Leafy lettuce [9].

Hyperbolic geometry has many interesting properties that counter our ingrained Euclidean intuition. To understand them, we will explore an important model of hyperbolic space: the Poincaré disc model.
The Poincaré disc model
We can imagine hyperbolic space as an open disk in the complex plane $\C$. We think of the space in the disk getting infinitely more “dense” as we approach the boundary of the disc, so the distance of a straight line between two points get longer as we approach the boundary. Thus, the shortest path between two points may be curved to take advantage of the “less dense” area towards the center of the disc. It turns out that the shortest distance between two points lies along the arc of a circle that is perpendicular to the boundary. In Figure 6, the shortest distance, called a geodesic, between A and B is the arc length of the given circle. Thus, the idea of “lines” in Euclidean space is generalized when in hyperbolic space to include circles.
This disc model is precisely what Escher saw in Coxeter’s book, and is what he used to create his art.

Figure 6. A geodesic between points A and B (created with GeoGebra).

Polygons in hyperbolic space
Since lines in hyperbolic space differ from our intuition about lines in Euclidean space, we must adjust our understanding of polygons as well. A hyperbolic polygon is a region of the hyperbolic plane whose boundary is decomposed into finitely many generalized line segments (recall that this includes circle segments), called edges, meeting only at their endpoints, called vertices. At most two edges can meet at any one point [1].
Earlier we mentioned that Euclid’s axiom that fails in hyperbolic space is used to prove that triangles have an interior angle sum of 180˚. Since this axiom does not hold, we need a new framework for thinking about polygons in hyperbolic space. In particular, Euclidean rectangles–quadrilaterals having four 90˚ angles–do not exist in hyperbolic space.
The basis for the polygon framework in hyperbolic space is the Gauss-Bonnet formula, which tells us that the area of a convex geodesic n-gon is $(n-2)\pi$ minus the sum of the interior angles [10]. Let’s take a moment for this to sink in–the area of polygons in hyperbolic space is dependent completely on angles! This goes against our Euclidean intuition, which tells us that a triangle with longer side lengths has a larger area than a triangle with shorter side lengths, despite the fact that both have angle sums of 180˚.
Armed with this knowledge that hyperbolic space gets more “dense” along with these new ideas about polygons, we are ready to dig in to the math of Escher’s works: hyperbolic tessellations.

Tessellations of hyperbolic space
Anyone who has looked at a tiled bathroom floor is familiar with the idea of tessellations: If we repeat a pattern of polygons, we can create a pattern over a large space. Someone who has attempted to tile their own bathroom floor may have noticed that not all tile shapes fit together nicely in a pattern. Note that a bathroom floor is an example of a Euclidean space, a geometry in which it turns out to be relatively difficult to happen upon a true tessellation. In contrast, hyperbolic space is relatively easy to tessellate.
Formally, a tessellation is a polygonal tiling of a plane that covers the entire plane. The Tessellation Theorem states that any polygon tiling in a complete space with the angles around any vertex adding to $\frac{2\pi}{n}$ for some integer n > 0 will be a tessellation of the plane. This holds true for Euclidean, spherical, and hyperbolic geometries.

When thinking about the increased “density” as we approach the edge, it should not be surprising that polygons appear smaller as we approach the boundary. Despite this, the areas stay constant (recall that it depends only on the angles!).

Escher’s tessellations
Escher created five works inspired by hyperbolic plane tessellations: Circle Limits I-IV and Snakes. While Circle Limit II and Snakes are beautiful (I highly recommend looking them up), in them Escher took more artistic license in tessellating the hyperbolic plane than the others. Thus, we will investigate Circle Limits I, III, and IV, all of which are wood cuts. His goal with creating these was to depict infinity in a finite space.

Figure 7. Polygons on Circle Limit I [5].

Circle Limit I
This is Escher’s first attempt at his exploration of hyperbolic tessellations, and my least favorite. I find it so be harsh and too sharp to be aesthetically pleasing.

As you can see from Figure 7, we can find both hexagonal and quadrilateral tessellations [5].

Notice that the Euclidean side lengths and areas of the polygons diminish as we approach the edge. Just how much do they scale? The answer comes from the distance formula for hyperbolic geometry–analogous to $d=\sqrt{x^2+y^2}$ in Euclidean geometry. It turns out that lengths are inversely proportional to the distance to the boundary. That is to say, a segment half way between the center and the boundary has twice the Euclidean length of one that is one quarter of the way from the boundary to the center. Since Euclidean area is related to edge lengths, the areas share this same relationship.

Escher was displeased with the result of this piece because the fish aren’t all facing the same direction, the coloring doesn’t alternate well, and the fish do not look realistic [3]. His Circle Limit III will resolve these self-criticisms.

Figure 8. Circle Limit III with the central tile of the octagonal tessellation [7], (polygon made using GeoGebra).

Circle Limit III
Circle Limit III is my favorite of the tessellations. In this work, the fish are nicely organized, their coloring properly alternates, and the images look more like real animals. This is achieved by alternating between triangles and quadrilaterals (as you can see from the defined white spines).

Although this image is more aesthetically pleasing, it did not pass the mathematical scrutiny of our very own Coxeter. As we discussed earlier, geodesic polygons must be made of perpendicular circle segments, but the arcs in Circle Limit III meet the boundary at about 80˚. An alternative view on the polygons, though, gives a true tessellation with octagons [5]. The center polygon is indicated in Figure 8, and the rest of the tiles can be found in the same way, by connecting the nose vertices and the fin vertices. Notice that the edges of the polygon are not straight lines, and are instead segments of circles perpendicular to the boundary of the disc.

Figure 9. Circle Limit IV [7].

Circle Limit IV
Circle Limit IV (Figure 9) is the last piece in the series, and plays with negative space to alternate angels and devils. It is commonly referred to as “Heaven and Hell,” and creates a hexagonal tiling–can you find it? (Hint: look at toes and wing tips to find vertices). Check this link to see if you found it. Escher also made a similar Euclidean tiling: Notebook Pattern or Symmetry Work 45 (1941) [6].

Today, most geometers use computers to study and create tessellations and other geometrical phenomena. The fact the Escher created these using only a compass and ruler is nothing short of miraculous. (This  column explores the nuts and bolts of how he could have achieved that–an especially hard task considering he was working in wood cuts). And recall that Escher was working not only without the aide of technology, but also without the aide of a formal math education. Keeping that in mind, although the technicalities of non-Euclidean spaces can be daunting, the mathematical beauty that arises from hyperbolic geometry are within your grasp, too.

References

[1] Bonahon, Francis. Low-Dimensional Geometry: From Euclidean Surfaces to Hyperbolic Knots, American Mathematical Society, 2009.
[2] Casselman, Bill. How Did Escher Do It?, America Mathematical Society Feature Column.
[3] Dunham, Douglas. Transformation of Hyperbolic Escher Patterns, University of Minnesota-Duluth.
[4] Mackenzie, Dana. The Universe in Zero Words, Elwin Street Press, 2012.
[5] Math & the Art of MC Escher. Hyperbolic Geometry, EscherMath, 2016.
[6] Math Explorer Club. M. C. Escher and Hyperbolic Geometry, Cornell University, funded by the National Science Foundation.
[7] MC Escher, website.
[8] National Geographic. Nudibranchs Photo Gallery.
[9] Organic Facts. Health Benefits of Lettuce.
[10] Schwartz, Richard Evan. Mostly Surfaces, American Mathematical Society, 2011.

This entry was posted in Uncategorized. Bookmark the permalink.

• ## Delauney Triangulations and the Traveling Salesman

The Traveling Salesman and Delauney Triangulation

By Aaron Liu

To quote Death of a Salesman, “A salesman is got to dream, boy”, it is easy to understand the struggles that come with being a traveling salesman. I like to think that the main character was dreaming of a quick way to approximate a path from his starting location to every city and back. I know that that might not have been his exact dream, but if I were a salesman I would dream of a solution to this problem.

It is hard to imagine the struggles of the traveling salesman, but if you take a quick look at the picture below, you will understand why a salesman must dream. Must I remind you that the distance from Boston to California as shown on the map is approximately: 3,109.3 miles. That’s about 5003.9333 kilometers for all of my European readers.

Currently there is no effect method of solving this problem for all situations. There are no known algorithms that will work 100% of the time and a lot of people have come to accept that fact (not me). But, there are ways to approximate solutions to the traveling salesman problem and one way involves topology. More importantly, I’m going to use the brilliant work of Boris Delauney and his triangulation in order to detail the approximations.

Triangulation Basics

I bet you are wondering how to create a Delauney Triangulation. Lucky for you I’m about to explain just that. Let’s start off with a simple graph in order to understand the basics.

In order create a Delauney Triangulation we need to consider all of the circles around sets of 3 points. Generally, if we start on the outside we can work our way inward. These such circles are called circumcircles and the key aspect is the fact that no point on the graph is inside a circumcircle. This may sound very complex and hard to achieve and that may be true for huge graphs, but for our example the Delauney Triangulation is actually quite simple.

It is easy to picture if you isolate the circles. Notice how the circumcircles overlap, but no point is inside of a circumcircle. Above all of the circles created is the triangulation that we wanted. The triangles are created by the circumcircles. Every point is connected with an edge to points that it shares a common circle with. It is important to note that if there is ever a circle with four points on it, the Delauney Triangulation will not exist. Conceptually this is makes sense because if that were allowed, we might have to call it a Delauney Polygonation. Sorry for that terrible joke.

In any event, the circumcircles allow us to create the triangulation and also give the triangulation some key features. But, first here are some important concepts.

Important Concepts:

A simplex is a dimensional piece of the whole. A 0-simplex would be a point, a 1-simplex would be a line segment, a 2-simplex would be a triangle, a 3 simplex would be a tetrahedron and so on.

Also the convex hull is the points such that all other points can be contained within those points. In the graph below the points P0, P1, P3, P10, P12 are the convex hull.

Now that you are enlightened with those key definitions, here are some key features of the triangulation:

• The union of all the simplicies is the convex hull of the points
• The triangulation maximizes the minimum angle of the triangles

This second characteristic means that the smallest angle of a triangle in the triangulation tends to be high. The triangulation rarely has scalene triangles because that would mean that two of the points were close together and the other was far away. This rarely occurs because if that were the case then the circle would likely be much bigger and has a higher chance of containing a point on the interior.

Delauney triangulations are derived from Voronoi diagrams. A Voronoi diagram can be created by connected the centers of the circumcircles of a Delauney triangulation. If you want to know more about the diagrams, take a quick look at Vlad’s post.

If not, or you believe you have a strong grasp on the triangulation, continue reading about the traveling salesman.

Delauney Triangulation and the Traveling Salesman

After seeing the above triangulation, it is hard to obviously see how the triangulation can be used to find a shortest path. The importance of approximating the traveling salesman problem is the quickness and in this situation, the ability to find a working solution. In the case of a Delauney Triangulation we can use the fact that none of the points are inside any other triangle. This is important because that means the triangulation has edges between points that are the closest to each other. It also gives us enough edges that we can construct a fairly accurate approximation.

Delauney Triangulations simply approximate so there are a lot of different algorithms that can be used. Also, the algorithms tend to grow to many and many lines of code that are very difficult to understand. Thus, I will explain a few such algorithms.

Algorithm Basics

Constructing an algorithm to approximate the shortest path using Delauney Triangulations can be very difficult. However, a lot of the characteristics of the Delauney Triangulation are very relevant to creating a shortest path algorithm.

Consider the following Delauney Triangulation:

Looking at this triangulation it is easy to see how an approximation to the shortest cycle could exist. The edges minimize the distance between the points and allow us to connect all points of the graph. Also, it is important to note that the amount of edges needed to be checked is much less than if there had been an edge between each vertex.

In order to find an approximation you can systematically check and eliminate unnecessary edges of the graph. The methods of doing this will vary greatly and will have to be very specific. The level of accuracy of the approximation will depend on how the edges are checked and removed.

Algorithms

The easiest method of doing this would be a brute-force check of all of the possible paths and eliminate the edges that are not in it. This method can be time-consuming, but would still be comparatively fast and accurate.

Another method would be a variation of the brute-force, but would compare the edges used in the path to the length of the path. The algorithm would look for certain edges that are contained in longer paths and would eliminate them. The algorithm would continue to eliminate edges, which would decrease the amount of work needed to find an approximation.

There are so many different variations of an approximation algorithm because after all it is approximation. One last algorithm that might be useful is checking a random amount of random paths and simply returning the path that produced the smallest distance. This obviously is not as accurate as the other algorithms, but is nonetheless useful if a quick solution is needed.

These algorithms are similar to an algorithm implemented by Christine T. Phan. Her paper can be found here.

It is important to note that at the end of her paper she states her results. She said on average Delauney Triangulations contained about 99.28% of the edges in the true shortest path. Using her own algorithm, similar to the ones described above, she was able obtain a 76.1% accuracy with her approximations. Although that number is not incredibly high, the results show that there are algorithms that will accurately approximate solutions to the problem. Perhaps, you will one day develop such an algorithm.

Conclusion

It has been shown that although Delauney Triangulations do not necessarily contain the optimal path, the triangulations contain edges that are in the optimal path. Thus, the quick approximation is very valuable and non-time-consuming. Delauney Triangulations are constructed in a way that is ideal towards finding a shortest path. Below are some resources that you can read if you want to learn more about Delauney Triangulations and the Traveling Salesman Problem. I guess until you do some more research and look into solving the problem, a salesman will just continue to dream.

Aaron Liu was a student in Scott Taylor’s Fall 2014 Topology class.

References:

http://www.geom.uiuc.edu/~samuelp/del_project.html

http://en.wikipedia.org/wiki/Delaunay_triangulation

http://oas.uco.edu/00/Papers/phan.htm

http://www.nytimes.com/interactive/2012/03/01/theater/201203-death-of-a-salesman-interactive.html

http://kiharalab.org/3d-surfer/v1.0/convex_hull.gif

This entry was posted in Uncategorized. Bookmark the permalink.

• ## Topology & Infinite-Dimensional Linear Algebra

For the student wishing to see interplay between the three major branches of mathematics (analysis, algebra, topology), Hilbert Space is a great place to explore!  Hilbert Space is a tool that gives us the ability to do linear algebra in infinite dimensions.  The very fact that infinity is involved should tell us that we will need analysis, and where ever there’s analysis, there’s also topology.  Oftentimes, interplay between analysis, algebra, and topology is not glimpsed at the undergraduate level; such connections are designated as “grad school material”.  Hilbert Space will offer us a chance to see these connections at work. Rather than give a host of definitions that define Hilbert Space and then give an example, it will perhaps be useful to work in the reverse order.  Consider the set of all complex-valued sequences.  An element of this set might look like this: $(4+ i, 3 - i, 1 - 7i, 5, 0, 5-9i, 2i,\ldots)$.  We look at a special subset:  let $\ell_2$ be the subset consisting of sequences that are square summable; that is, the sequences $(x_n)$ satisfying

$\sum\limits_{i=1}^\infty {\vert x_{i} \vert}^2 < \infty$.

It shouldn’t be entirely clear why we are interested in sequences satisfying this seemingly arbitrary condition, but shortly we will see its importance.  Notice the similarity between the dot product and the infinite sum on the left – the sum looks a lot like the dot product of a vector in $\mathbb{C}^n$ with itself.  The set $\ell_2$ is an example of Hilbert Space; it is just the natural extension of $\mathbb{C}^n$.  We will work a lot with $\ell_2$, but first let’s make sure we really understand this space.  We set out on defining Hilbert Space – a fairly tall order as we shall see!

David Hilbert first introduced the concept of Hilbert Space

This may sound intimidating; it shouldn’t be. A Hilbert Space is just a very special type of vector space. Recall from linear algebra that a (real or complex) vector space $V$ is a set that is closed under addition and scalar multiplication (by real or complex numbers). We call a subset $B$ of $V$ a basis if $V = span(B)$ and if $B$ is linearly independent. In this case we define the dimension of $V$ by saying $dim(V) = \vert B \vert$. Notice that there is nothing about this definition which requires $B$ to be a finite set. Indeed, while finite dimensional vector spaces are the primary object of consideration in linear algebra, so-called infinite dimensional vector spaces are the central object in a subject called operator theory, and Hilbert Space is to operator theory what $\mathbb{R}^n$ and $\mathbb{C}^n$ are to linear algebra. We need a few preliminary definitions in order to define a Hilbert Space. We will work over $\mathbb{C}$ (it is no more difficult to do so than to work over $\mathbb{R}$). We first define an inner product on a vector space $V$.  An inner product is just a generalization of the dot product on $\mathbb{R}^n$ or $\mathbb{C}^n$.  Recall the importance of the dot product: it gives us a notion of length, angle, and orthogonality.  So an inner product on an arbitrary vector space is a way of giving the space some geometry. An inner product is denoted $\langle \cdot , \cdot \rangle$, and we replace the dots with vectors to indicate that we’re taking the inner product of those two vectors.  Of course, there is a more rigorous, axiomatic definition.  For thoroughness, we state this definition, but it can be safely ignored without loss of understanding later on.  An inner product on a vector space $V$ is a function from $V \times V$ to $\mathbb{C}$ that satisfies the following four rules:

1. $\langle a + b, c \rangle = \langle a , c \rangle + \langle b , c \rangle$ for every $a, b, c \in V$.
2. $\langle \lambda a , b \rangle = \lambda \langle a , b \rangle$ for every $a, b \in V$, $\lambda \in \mathbb{C}$.
3. $\langle a , b \rangle = \overline{\langle b , a \rangle}$ for every $a, b \in V$.
4. $\langle a , a \rangle$ is real and greater than $0$ if $a \neq 0$.

Note that if we were working over $\mathbb{R}$, property (3) would just say that the inner product is symmetric.  We call a vector space with an associated inner product an inner product space. Recall that the definition of the dot product on $\mathbb{C}^n$ is $x \cdot y = \sum\limits_{i=l}^n x_{i}\overline{y_{i}}$, where $x_{i}$ and $y_{i}$ are the components of $x$ and $y$, respectively. The dot product satisfies all the properties above, and so it is an inner product on $\mathbb{C}^n$.  Once one has verified that the dot product on $\mathbb{C}^n$ is an inner product, it is not too hard to convince oneself that the extension of the dot product to $\ell_2$ is an inner product as well.  We define an inner product on $\ell_2$ by

$\langle x , y \rangle = \sum\limits_{i=1}^\infty x_i \overline{y_i}$

An example of a norm, just the usual distance function on the plane

The square summable condition we imposed on $\ell_2$ suddenly makes sense.  If we tried to compute the above inner product on sequences that are not square summable, we might end up with a divergent series on the right side of the equation – and we don’t want that! We define the norm of an element $v$ in an inner product space $V$ to be $\Vert v \Vert = \langle v , v \rangle ^\frac{1}{2}$. We will denote the norm on $\ell_2$ by ${\Vert \cdot \Vert}_2$.  Notice that if one applies this definition to $\mathbb{R}^n$, the norm of a point is just its distance in the origin.  So we think of a norm as a function that assigns lengths to vectors in our vector space.  In general, a norm is any function $\Vert \cdot \Vert: V \to \mathbb{R}$ that satisfies the following three axioms:

1. $\Vert x \Vert \geq 0$ for all $x \in V$, with equality if and only if $x = 0$.
2. $\Vert \lambda x \Vert = \lambda \Vert x \Vert$ for all $x \in V$, $\lambda \in \mathbb{C}$.
3. $\Vert x + y \Vert \leq \Vert x \Vert + \Vert y \Vert$ for all $x,y \in V$.

One can verify that any inner product induces a norm. Although we defined the norm in terms of an inner product, we say that any function satisfying (1), (2), and (3) is a norm, whether or not it is given in terms of an inner product. So, any inner product defines a norm, but not every norm is given by an inner product. For example, it is impossible to define an inner product on $\mathbb{R}^2$ such that the induced norm is $\Vert (x,y) \Vert = max\{ \vert x \vert , \vert y \vert \}$.

Sequences of rational numbers can ”converge” to irrational numbers, so the rationals are not complete

We need one more definition before we can define a Hilbert Space. We need the concept of completeness. This is a fundamental property of the real numbers – completeness is what allows us to do real analysis. Essentially a space is complete if there are no “gaps” in it. For example, $\mathbb{Q}$ is not complete because the sequence $3, 3.1, 3.14, 3.141, 3.1415, \ldots$ should converge, but it doesn’t (in $\mathbb{Q}$). Such a gap does not exist in $\mathbb{R}$, so we say the reals are complete. We are now in a position to define a Hilbert Space: a Hilbert Space is a complete vector space equipped with an inner product. A similar structure is a Banach Space, which is a complete vector space equipped with a norm. So any Hilbert Space is a Banach Space, but the converse is not true. We can immediately get our hands on some Hilbert Spaces: $\mathbb{R}^n$ and $\mathbb{C}^n$ are both finite-dimensional Hilbert Spaces. These are not particularly interesting Hilbert Spaces because they are finite-dimensional. But we are also ready to consider an infinite-dimensional Hilbert Space.  As we stated before, $\ell_2$ is a Hilbert Space.  It is not difficult to show that $\ell_2$ is a vector space, and we’ve already defined an inner product on it.  Showing that $\ell_2$ is complete does take a bit of work, but it’s doable.  We can also readily see that $\ell_2$ has no finite basis.  Indeed, an example of a basis for $\ell_2$ is the collection of sequences $e_{i} = (0, 0,\ldots, 1, 0, 0,\ldots)$ where the $1$ appears in the $i^{th}$ entry.  Of course, there are many other examples of Hilbert Spaces, but a somewhat remarkable fact is that every Hilbert Space that has a countable (indexed by $\mathbb{N}$) basis is isomorphic to $\ell_2$! For this reason, mathematicians sometimes refer to “the” Hilbert Space, as if there is only one. The upshot is that we can work exclusively in $\ell_2$ without sacrificing the generality obtained by referring to a general Hilbert Space.

A rotation about the origin is a linear operator on the plane

Since $\ell_2$ is a vector space, the natural thing to do is think about linear transformations of the space.  We define a linear operator on $\ell_2$ in the same way a linear transformation is defined in linear algebra. A function $T: \ell_2 \to \ell_2$ is a linear operator if

1. $T(x+y) = T(x) + T(y)$ for every $x,y \in \ell_2$.
2. $T(\lambda x) = \lambda T(x)$ for every $x \in \ell_2$ and $\lambda \in \mathbb{C}$.

It should be noted that not everything one may have learned about linear transformations in linear algebra is true for linear operators on $\ell_2$. For example, consider the shift operators $S$ and $S^*$ on $\ell_2$ defined by $S(x_1,x_2,x_3,\ldots) = (0,x_1,x_2,\ldots)$ and $S^*(x_1,x_2,x_3,\ldots) = (x_2, x_3,x_4,\ldots)$. It is easily verified that these are both linear operators, and that $S$ is injective but not surjective, $S^*$ is surjective but not injective, and $S^*S = I$ but $SS^* \neq I$. In linear algebra, one learns that all of these conditions are equivalent, but in Hilbert Space this is not the case.  An important part of operator theory is determining what kinds of operators on $\ell_2$ behave like linear transformations on a finite-dimensional vector space.

We call a linear operator $T$ on $\ell_2$ bounded if there is a constant $M$ such that $T$ is bounded on the unit ball $\mathbb{B} = \{ x \in \ell_2 : {\Vert x \Vert}_2 \leq 1 \}$ by $M$. The norm ${\Vert T \Vert}_{op}$ of a linear operator is defined to be the smallest such $M$ that works in the preceding definition. Equivalently, ${\Vert T \Vert}_{op}$ is the largest value of ${\Vert T(x) \Vert}_2$, where $x$ ranges over the unit ball in $\ell_2$. An interesting fact about linear operators on $\ell_2$ is that they are continuous if and only if they are bounded (an exercise!). We define $B(\ell_2)$ to be the set of all bounded (continuous) linear operators on $\ell_2$.

$B(\ell_2)$ is an interesting space in and of itself: equipped with the norm defined in the preceding paragraph, $B(\ell_2)$ is a Banach Space (a complete normed vector space) with respect to pointwise addition and multiplication by complex scalars. We have seen a little bit of analysis and algebra, so it’s time to introduce some topology to the mix. Our goal is to define and understand some topologies on $B(\ell_2)$. This should be a bit surprising. After all, what does it mean for a subset of linear operators to be “open”? There are many topologies that can be put this set, but we will consider the three most common ones: the norm topology, the strong operator topology, and the weak operator topology. In describing a topology on a space, it is difficult to pin down exactly what the topology is; this is because in most interesting spaces, there are so many open sets that it’s impossible to list all of them. Instead we can define a topology by describing what properties our set has when equipped with this topology. For example, we might say that a topology on a set $A$ is “the smallest topology such that our space $A$ has property $X$“. We can also define a topology in terms of a base which, roughly speaking, is a collection of open sets that generates the rest of the open sets (by taking unions). Before we embark on defining different topologies on $B(\ell_2)$, let’s stop and think about why we may need different topologies on the same set, and whether it is of real importance. A question one may ask is, “What properties of $B(\ell_2)$ will change when the topology changes?” As we will see shortly, the definition of convergent sequence changes drastically. It may not seem obvious that changing the topology will have a big effect on convergence of sequences; after all, the definition of convergence that one meets in a real analysis course does not explicitly mention open sets! But let’s examine this a little closer. In real analysis, convergence is usually defined in regards to a metric. In more general topological spaces, there may be no metric (although in Hilbert Space the metric is induced by the norm), so the definition from real analysis may not be applicable. Nevertheless, we can define convergence in terms of open sets thusly (and this definition works in every topological space, including metric spaces):

Take an open interval about 1 on the vertical axis and eventually, all but finitely many points are in this interval

Let $(x_n)$ be a sequence in a topological space $X$.  We say $x_n \to x$ if for every open set $U \subset X$ containing $x$, we have $x_n \in U$ for sufficiently large $n$. It is clear, now, that convergence depends on the definition of open set. As we introduce new topologies on $B(\ell_2)$, we can describe what convergence “means” with respect to this new topology.

The norm topology on $B(\ell_2)$ is the topology induced by the operator norm. To explain what this means, let us consider that any normed space has a corresponding topology induced by its norm. Think about $\mathbb{R}$ for example. The norm of a point in $\mathbb{R}$ is

The open set O(1.5, 1.5)

just its absolute value. Think about the subsets of $\mathbb{R}$ defined by $O(x,\epsilon) = \{ y \in \mathbb{R}^2 : \vert x - y \vert < \epsilon \}$, where $x \in \mathbb{R}$ and $\epsilon$ is a positive real number. Each set is an open interval centered at $x$ and of radius $\epsilon$. The open sets in $\mathbb{R}$ are open intervals and unions of open intervals, so the collection $\{O(x,\epsilon) : x \in \mathbb{R}, \epsilon > 0 \}$ is a base for the usual topology on $\mathbb{R}$. Now we return to our set $B(\ell_2)$, where the norm topology will be defined analogously. The collection of all subsets of $B(\ell_2)$ of the form $O(T, \epsilon) = \{ S \in B(\ell_2) : {\Vert S - T \Vert}_{op} < \epsilon \}$ is a base for the norm topology on $B(\ell_2)$.  Remember that a norm is a way of defining length or distance in our space.  So the set $O(T, \epsilon)$ is the set of all operators that have distance from $T$ less than $\epsilon$.  It probably seems odd think about the distance between two functions – this is why we need careful and precise definitions of norms and, in particular, the operator norm.  The norm topology is a very important topology on $B(H)$ indeed – it is the topology which makes $B(\ell_2)$ a Banach Space.

Before looking at any special properties of the norm topology, we introduce the next topology on $B(\ell_2)$ because the interesting thing to do is to compare the different topologies. Next we consider the Strong Operator Topology (SOT). The SOT is defined to be the smallest topology containing all sets of the form $U(T,x,\epsilon) = \{ S \in B(\ell_2) : {\Vert S(x) - T(x) \Vert}_2 < \epsilon \}$ where $T$ is any bounded linear operator, $x$ is any element of $H$, and $\epsilon$ is any positive real number. Equivalently, SOT is the smallest topology on $B(\ell_2)$ such that the evaluation maps $T \mapsto T(x)$ are continuous for every choice of $x \in \ell_2$. A word of caution: The sets $U(T,x,\epsilon)$ may seem very similar to the sets we defined in the previous paragraph, but they’re not. Notice that we use the $\ell_2$ norm here, and the operator norm in the preceding paragraph. It is important to keep track of which norm function is being used and what quantity is inside the norm – of course, it wouldn’t make sense to take the operator norm of the quantity $S(x) - T(x)$! We can describe some of the properties of the SOT. The SOT is (somewhat paradoxically) weaker than the norm topology; that is, there are more open sets in the norm topology than there are in the SOT. The SOT is perhaps a more natural choice of topology on $B(\ell_2)$. To explain this, I first pose a question: what does it mean for a sequence of bounded linear operators $(T_n)$ to converge to an operator $T$? Well, it depends on which topology you use! In the SOT, the sequence $(T_n)$ converges to $T$ if for every $x \in \ell_2$, the sequence $(T_n(x))$ converges to $T(x)$. That is, convergence in SOT means that a sequence of operators converges pointwise to some operator. This indeed seems like a very natural definition of convergence. Contrast this with convergence in the norm topology: the sequence $(T_n)$ converges to $T$ in the norm topology if ${\Vert T - T_n \Vert}_{op} \to 0$.  In a way, this definition of convergence seems more complicated and less natural than convergence in SOT.  This already is an advantage of using SOT instead of the norm topology. We mentioned that SOT is weaker than the norm topology. It isn’t too difficult to show that convergence in the norm topology implies convergence in SOT (for the reader who wants a challenge: assume ${\Vert T_n - T \Vert}_{op} \to 0$. Pick $x \in \ell_2$ and show $T_n(x) \to T(x)$). Using the given definitions of convergence in each topology, we can show that the converse is not true. Consider the following sequence of operators $(P_n)$ on $\ell_2$:

$P_n(x) = \sum\limits_{i=1}^n \langle x , e_i \rangle x$,

where $\{e_i\}$ is the basis we defined earlier. The operators $P_n$ are called projections, because they take an input $x$ and project $x$ onto the linear span of the first $n$ basis vectors. It is not hard to see that as $n \to \infty$, we have $P_n(x) \to x$, i.e. $P_n \to I$ in SOT ($I$ is the identity operator). However, the claim is that $P_n \nrightarrow I$ in the norm topology.  We will just sketch a proof here.  Let $m,n \in \mathbb{N}$ with $m > n$.  Then find a lower bound on ${\Vert P_m - P_n \Vert}_{op}$ (a bound of 1 is easy to obtain by picking the unit vector that has a $1$ in the $m^{th}$ entry and else all zeroes).  What this tells us is that every element of the sequence is at least distance 1 from every other element of the sequence, and clearly no sequence with this property can converge.

The third and final topology we introduce on the space $B(\ell_2)$ is the Weak Operator Topology (WOT). The WOT is the smallest topology on $B(\ell_2)$ containing the following sets $U(T,x,y,\epsilon) = \{ S \in B(\ell_2) : \vert \langle T(x) - S(x) , y \rangle \vert < \epsilon \}$, where $T \in B(\ell_2)$, $x, y \in \ell_2$ and $\epsilon$ is a positive real number. Equivalently, the WOT is the smallest topology such that the map (called a linear functional) $T \mapsto \langle T(x) , y \rangle$ is continuous for any choice of $x, y \in \ell_2$.  So a sequence of operators $(T_n)$ converges to an operator $T$ if $\langle T_n(x) , y \rangle \to \langle T(x) , y \rangle$ for every choice of $x, y \in \ell_2$.   In order for the names given to these topologies to make sense, we had better hope WOT is weaker than SOT. Alas, this is indeed the case. Again, it is not hard to prove that SOT convergence implies WOT convergence (the only part that may be difficult is to show that an inner product is continuous). Again we can show the converse does not hold. Recall the definition of the shift operator $S$ on $\ell_2$. Define $S_n$ by composing $S$ $n$ times. That is, $S_n(x_1, x_2, x_3,\ldots) = (0, 0,\ldots,x_1, x_2, x_3,\ldots)$ where the sequence on the right starts with $n$ zeroes. First we can show that $S_n \nrightarrow 0$ in SOT. Consider $x = (1,0,0,\ldots)$. Then the sequence $(S_n(x))$ does not converge to the $0$ sequence. To see this, take any $m,n \in \mathbb{N}$ with $m \neq n$. Then $S_m(x) - S_n(x)$ is a sequence with $1$ in the $m^{th}$ entry and $-1$ in the $n^{th}$ entry, hence we have ${{\Vert S_n(x) - S_m(x) \Vert}^2_{2}} = 2$. Since this is true for any choice of $m$ and $n$, the distance between any two distinct points in the sequence $(S_n(x))$ is $\sqrt{2}$.  So the sequence does not converge to any limit, including $0$. It is harder (but not too difficult) to show that $S_n \to0$ in WOT. The reader who wishes to provide a proof of this statement may want to read about linear functionals and the Riesz Representation Theorem.

Of course, there is much more to say about Hilbert Space (and even about $B(\ell_2)$ than I could fit into this post.  Hilbert Space could easily be the sole focus of a semester- or even year-long course.  In his Mathematics: a Very Short Introduction, mathematician Timothy Gowers wrote, “The notion of a Hilbert Space sheds light on so much of modern mathematics, from number theory to quantum mechanics, that if you do not know at least the rudiments of Hilbert Space theory then you cannot claim to be a well-educated mathematician.”  Hopefully the reader leaves with an appreciation for the fact that Hilbert Space is a (relatively) easy space to understand and that algebra, analysis, and topology are all lurking around in Hilbert Space.

The author Dan Medici was a student in Scott Taylor’s Fall 2014 Topology class at Colby College.

This entry was posted in Uncategorized. Bookmark the permalink.

• ## Using Configuration Spaces to Find Inscribed Squares

As an undergraduate in mathematics, every once in a while, one of your math friends will send you a link to a very interesting unsolved problem in mathematics.  I made the mistake of clicking on one, because after reading it, it captivated my mind for weeks: “The Inscribed Square Problem.” Now, this conjecture says that for any simple closed curve (Jordan curve), there is a square whose corner points all lie in the curve. On first examination, I thought to myself, “wow there’s no way this is true, there are some pretty messed up curves out there, and I bet there’s at least one of them where this does not hold.” So I went to talk to my topology professor about this and we talked about a method of approaching this problem using configuration spaces, which I will talk a little bit about in this blog post.

First we will start off by explaining exactly what a configuration space is. A configuration space is a way to topologically represent how objects can be placed and moved around within certain spaces. For example, if you have a circle and you want to place two points on it, you might start by thinking that for every place you put your first point, the places that you could place the second point can be represented by a circle with a point removed (because both points cannot be in the same place), and so it turns out that the configuration space of two points in a circle (denoted $C^2(S^1)$ where $S^1$ is the circle and the superscript 2 denotes how many bodies are in the space) is $S^1 \times(S^1 - \{a\})$ where a is a point on the circle. Now this is interesting, because $S^1 \times S^1$ is an interesting construction called the torus (it’s pretty much just a doughnut):

However, removing a point from the second circle transforms it into a line segment

so you end up with something similar to $S^1 \times (S^1 - \{a\})$ which looks like the result of rolling a piece of paper up. (Something akin to the outside shell of a hollow cylinder without the circles on the ends)

Now, while you may believe me when I say that each point on this gives a place for two positions on the circle, let us examine how this actually works, here I have drawn a circle with two points A and B on it (I have also drawn an arrow at the top as a reference point).  First let us choose our A position.  The place around the cylinder determines where our first point should go.  We want to place our A point somewhere on the cylinder where the dashed-and-dotted line is because that is where A is in relation to our point of reference (note that if we were to look at the cylinder from the top, that line would correspond exactly to where A is).  Now, the height at which we place our B point on the cylinder is determined by where in relation to A it is.  Here we can see that B is a little after A if we head clockwise around the circle.  So we can place B a little bit away from the top to get the point shown on our cylinder.  Note that this also demonstrates why the bottom and top of our cylinders are open, because as we get to the edges of the cylinder, we get closer and closer to the A point, but can’t actually reach it.  If we could, we could say that the top and bottom of our cylinder were essentially the same circle and “glue” them together to get the torus.

Now, a Jordan curve in the plane can be described as the image of an injective continuous function from the unit circle to the plane. Knowing that our goal is to try and determine whether it has an inscribed square, we should start by examining how 4 points can be configured on our curve, that is $C^4(\phi(S^1))$ where $\phi$ is our injective continuous function. Now, because our curve is continuous and does not cross over itself, it is essentially just a circle which has been squished and pulled to make it our circle, so by reversing our process (finding a continuous function which when composed with $\phi$ gives us a circle), we can deform it back into the circle:

and by doing this, we can notice a few things about the structure of our configuration space. Firstly we already know how to place 2 points on the circle, but we can also realize that placing four points on the circle is exactly the same as placing 2 points on the circle twice! (This is fairly obvious in real life, but its mathematical meaning has a bit more significance) that is

$C^4(S^1) = C^{2}(C^{2}(S^{1}))$

So, we can look at the configuration space of $C^2(\phi(S^1))$ and notice that it will be equal to

$C^{2}(C^{2}(S^{1})) = (C^{2}S^{1}))\times(C^{2}(S^{1})-\{a\})$

So what on earth does this mean? It means that for every point in one of our “cylinders” we can represent two point on the circle by placing one point in our cylinder-like construction and then placing our second point on a different cylinder-like construction with a point missing (Taking the cross product of the two spaces)

Alternatively, you could just declare your configuration space to be

$C^{4}(\phi(S^{1})) = \{(a,b,c,d)\in S^{1} | a\ne b\ne c\ne d \}$

But I find the first definition to be much easier to picture in my head than the second succinct but abstract one.
So, now that we have a rough picture of a configuration space for if our curve was a circle, remember that we simplified this by stretching it into a circle, now we can translate it back to our initial curve, $\phi$, by twisting and bending every circle that we encounter back into our Jordan curve (slightly more formally, we have been composing $\phi$ with a function which continuously deforms it into a circle.  At this point, we stop composing $\phi$ with that function).

Now, let us talk briefly about how we can define some fairly useful functions on configuration spaces.  First let’s look at the distance function $d:C^2(S^1)\rightarrow \mathbb{R}$.  First let us not that this function is continuous, if we change our point in the space by a tiny bit, the distance between the two points will not change drastically.  Also we can see that the closer you get to the edges of the cylinder, the closer the two points are (at the edges, they would occupy the same space), so from this, we can see that the maximum distance is the ring in the very center of our cylinder.  This is a very neat way of seeing that the points in the ring in the center of our cylinder occur exactly when our two points on the circle are placed opposite each other.

We can now define very useful function $f$ from $C^4(\phi(S^1))$ to the set {0,1} such that a point $x \in C^4(\phi(S^1))$ is mapped to 1 if one of the components (the points coming from each mutilated circle) $x_1$ is a distance c away from $x_2$ and $x_3$ and is a distance $c\sqrt{2}$ away from the third one, and furthermore, that $x_3,x_1,x_2$ form a right angle and that $x_1,x_2,x_4$ form a right angle. This will ensure that any point in the configuration space that would make a square in the original curve (remember that the configuration space has coordinates for four points on the curve) gets mapped to 1. Now, we can proceed from here in several different ways, we could take the preimage $f^{-1}(1)$ and determine if it is not empty, or we could define the topology on our configuration space to be the indiscrete topology, (the one where the only open sets are the empty set and the entire space), this has the benefit that the only functions which are continuous are constant functions. So, since there will be at least one point in our configuration space which gets mapped to 0 (otherwise every set of four points is an inscribed square, which is obviously not the case), so if $f$ maps a point to 1, it will be discontinuous, and so all we need to do is check to see if f is continuous.

Now, this is easier said than done, the nature of this function $f$ is such that determining whether it is continuous could be just as difficult as determining the truth of the original statement using geometric means. However, topology has many different ways of determining continuity, so it could just be that someone could come along and prove that this function is always discontinuous (meaning that the conjecture holds) or they use this method to construct a curve where our function is discontinuous (the conjecture does not hold)

We could also define a continuous function $f^\prime:C^2(S^1)\rightarrow \mathbb{R}^6$ whose components are the distances between two respective points.  We’ve already seen that the distance component is continuous, and so since its components are continuous $f^\prime$ will be continuous.  Now, we just have to see where in $\mathbb{R}^6$ the function would satisfy the conditions.  This is not too difficult, it is fairly common knowledge that for the four points in a square, the distance between four pairs of them will be equal, and the distance between the other two pairs will be equal as well.  So, any point in $\mathbb{R}^6$  where 4 of the components are equal and the other two are equal as well will do.  Now, since $f^\prime$ is continuous, we have many tools at our disposal to determine whether or not there is a point in its range which satisfies the conditions for being a square.

For more information on the inscribed square problem and what has been proven about it, visit this website

<i>Professor’s note:</i> Joseph took Topology from me (Scott Taylor) in the Fall of 2014. Although there some inaccuracies in the exploration of configuration spaces above, I was quite taken with the refreshing approach and tone of the piece, so I have left it unedited.

This entry was posted in Uncategorized. Bookmark the permalink.

• ## Algorithms for Working with Triangulated Surfaces

Let’s imagine that you and your friends just took out a steaming pepperoni pizza out of the oven. How would you go about triangulating (divide using triangles) the surface (the pizza) into equal pieces? This shouldn’t be to hard, should it? But what if someone took a knife and placed a couple of points on the pizza, and said the triangulation has to contain triangles that have those points as vertices. How would unite the dots, making sure that the triangles you get yield the fairest division? Not so easy is it?

This is a problem that most graphics software engineers encounter. But their conundrum is even more complicated as they deal with millions of points located in 3D space, and the process they’re using has to be automated and work for every possible case. Because we will use this problem to guide us through the concepts presented in this post, we should first offer a clear description of the problem and of the solution we are looking for. In Computer Graphics, models (let’s say a human face) are made of thousand of patches that consist of a fixed number of points (usually numbers that are perfect squares). These points keep track of their position in 3D space (these are called world coordinates, as they lie in the coordinate system of the model). Because the computer programmer wants to create a realistic human face while making his program fast, he or she devises an algorithm that subdivides the patches into subpatches that have less than a certain distance in screen coordinates between adjacent points (i.e. the distance between two points on the screen will be smaller than an certain limit). This way, instead of having nice patches made out of 16, 25 or 36 points, we end up with all sorts of random configuration of points. And we have lots of such configurations. We are interested in finding an algorithm that, after the aforementioned subdivision, is able to create a triangulation of all the points in the model, while rendering an image as realistic as possible. By realistic, we understand that we don’t want our triangles to be too skinny, too big or too small, because that would create a deformed face (not that every face isn’t beautiful in its own way). Also, we are not allowed to have edges crossing each other (because that wouldn’t be a triangulation anymore), and we are not allowed to add new points.  To keep the problem simple, we will ignore things like aliasing and hidden surface removal, and we will also reduce our example to two dimensions. The presented method works in all dimensions, and the problem can actually be reduced to two dimensions by creating a bounding cube around the object and reflecting the points onto the closest face).

This is the kind of result we are looking for. Note that in this case, a different type of subdividing from the one we presented is used. The points are more dense in regions were the protuberances of the faces are more pronounced.

This is how we can reduce the problem from three dimensions to only two dimensions.

A mathematical structure that encompasses all of the above requirements is the Delaunay Triangulation. Before jumping into any algorithms, we shall first try to gain a mathematical understanding of Delaunay Triangulations. We can define Delaunay Trinagulations in two ways:

• Geometrically,  a Delaunay triangulation for a set P of points in a plane is a triangulation DT(P) such that no point in P is inside the circum-circle (the unique circle that passes through each of the triangle’s three vertices) of any triangle in DT(P) .
• Topologically, a Delaunay triangulation of a ﬁnite set ${{S}\subseteq \mathbb{R}^n}$ is isomorphic to the nerve of the Voronoi diagram of ${{S}}$.

As with most things in life, let us first ignore the harder definition and focus on the geometric one. The following image should make the definition clearer:

As you can see, the first picture is a Delaunay Triangulation because there are no points within any of the four circumcircles.

Because for our set ${{S} = \left\{ {A,B,C,D,E}\right\} }$ no points lie within the circumcirlces of triangles ${\Delta ABC,\Delta ACE,\Delta CED,\Delta BCD}$, then ${{DT(P)} = \left\{\Delta ABC,\Delta ACE,\Delta CED,\Delta BCD\right\}}$. Note that the triangulation of a set of points is a set of triangles. This definition is clear and easy, and it will be the one we will use when implementing our algorithm. However, why this specific triangulation works for our imposed conditions is not that apparent. If we take a look at the three triangulations above, we can observe that the Delaunay Triangulation is the most ‘aesthetically pleasing’ one, in the way that we don’t have long, slim triangles and that we only connect points that are close to each other. As it turns out, this ‘aesthetically pleasing’ property is given by the fact that Delaunay Triangulations maximize the minimal angle. In other words, the minimal angle of all the triangles in a Delaunay Triangulation of a set  ${{P}}$ , will be larger than the minimal angle of all the other triangulations of  ${{P}}$. Why does the property that no point of ${{P}}$ lies within the circumcircle of any triangle maximize the minimal angle? Pick a triangle in our triangulation and look at its least angle. Observe that as we move the vertex at that angle away from the center of the circle, two things happen: the circle increases in area along with the odds of another point of the set entering the circle, and the angle further decreases. So, because we are trying to form triangles with circumcircles that are as small as possible (ATTENTION: this is only an implication that is generally true, but it isn’t by any means a requirement, as Delunay triangulations don’t concern minimizing the edge length),we are ensuring that our triangulation connects points that are close and that we are avoiding ‘ugly’ triangles. This makes the Delaunay triangulation a perfect solution to our problem. Other properties of Delaunay Triangulations that we will take for granted are: every set of points in the Euclidean Space has a Delaunay Triangulation that is unique if no two points lie on the same sphere, the union of all the triangles form the convex hull of the set of points (i.e. the minimum convex set containing all the points in the set or a rubber band stretched using the points of the set so that it contains all of the points in the set in its interior).

Now let’s turn our attention towards the topological definition of a Delaunay Triangulation. At a first glance, the definition seems discouraging, but as we will set out to explain the terms, we will see that the sky isn’t that gray. The first word of the day is ‘isomorphic’, which for all intents and purposes means ‘the same’. The second math term is ‘nerve’. Lets look at the picture below and try to make sense of it:

The nerve(red) of a set of triangle (green)

Given a union of triangles ${{T_i}}$, we can form its nerve ${{N}}$ by following these steps. Start with  ${{N}}$ empty, and for each triangle in the union associate one point ${{t_i}}$ and add it to ${{N}}$. Then, look at non-empty intersections of the triangles(non-empty means that they share at least a point), and for every point shared by at least two triangles add a new set formed with the ${{t_i}}$‘s corresponding to the triangles that share that point. In this process you cannot repeat sets. If you correctly cover all the possible intersections, ${{N}}$ will be the nerve of the union of triangles. Observe that ${{N}}$ is a set containing sets of one or more points, sets which we can graphically represent through points, edges and polygons as seen in the picture above. The final unknown term is “Voronoi diagram”. Again, pictures comes in handy:

A nicely colored Voronoi Diagram of 20 points.

We form the Vornoi cell of a point P by taking the intersection of all the half-spaces that contain P.

The Voronoi diagram(the whole first picture) of a set of points(the black points) ${{S}\subseteq \mathbb{R}^n}$ is the collection of all the Voronoi cells(the colored polygons), denoted by ${{V_u}}$, where ${{u}}$ is a point of ${{S}}$ and ${{V_u} = \left\{x\in\mathbb{R}^n\mid \|x-u\| \le \|x-v\|,v\in\mathbb{R}^n\right\} }$. This definition tells us that every point in the cell ${{V_u}}$ is closer to ${{u}}$ than it is to any other point in ${{S}}$ and that the points on the edges of the diagram are equally distanced from the points that generate incident Voronoi cells.  So, using this definition, we can form the Voronoi cell of a point ${u\in{S}}$ by dividing the plane, for each other point ${v\in{S}}$, into two pieces(a.k.a. ‘half-spaces’) using lines that are equally far away from ${{u}}$ and ${{v}}$. Then, if we take the intersection of all the half-spaces that contain ${{u}}$, we will end up with ${{V_u}}$. Although the definition allows for building Voronoi diagrams for spaces with dimension greater than 2, it turns out that for computational purposes this is not feasible process, as it a huge amount of time and storage space.

Stereographic Projection

To plunge even deeper into topology, we present two more constructions for the Voronoi cells. To do this, we will go down one more dimension to create some visual intuition of the constructions, and then let the reader work his newly gained knowledge by extending the example to two dimensions. Use the picture bellow for reference. The Voronoi Diagram of a set ${{S}\subseteq \mathbb{R}^1}$ is nothing more than a segmented line, where the segments are the Voronoi cells(in our drawing, the Voronoi diagram of the set ${{S} = \left\{ {a,b,c,d}\right\} }$ is the segmented equator). We will lift our Vornoi cells to two dimensions by using stereographic projection. Intuitively, the stereographic projection of circle(sphere for two dimensions) is the shadow of its points cast by a single light on the surface of the circle onto a line(plane in two dimensions). By casting shadows, we mean picking a point ${{N}}$ and drawing lines from it that intersect both a point on the circle and the line . This creates a mapping( an isomorphism, if you will), between the circle minus the point ${{N}}$ and the line. So, we draw a circle that has our space as its equator, and take the north pole as our point ${{N}}$. Using the inverse of the stereographic projection of the circle(i.e. we start from points on our space and draw lines that go through ${{N}}$ and intersect the circle(the brown lines in our drawing)), we map our set ${{S} = \left\{ {a,b,c,d}\right\} }$ onto the circle. For the first construction, we will draw tangent lines to the circle at the newly obtained points. These are the Pa,Pb,Pc,Pd in our drawing. Look carefully at their intersections. It seems that if we were to draw a line connecting the intersecting points and ${{N}}$, we would intersect the line at the boundary of the Voronoi cells of the points that yielded the tangent lines. This turns out to be true. It is also true that if we draw lines from ${{N}}$ to the stereographic projection of the points in our space, the line which we will first intersect, corresponds to the Voronoi cell to which the point belongs. For our second construction, we can build circles(Ca,Cb,Cc,Cd) that contain both ${{N}}$ and the points in ${{S}}$ and that are tangent to the equator. Take a moment to convince yourself that these circles are unique. Again look at the points of the intersections of the circles and remark that a line containing ${{N}}$ and any of these points will also contain the boundary of two Voronoi cells. Thus, the first intersection of the segment connecting a point in our space and ${{N}}$ is with the circle corresponding to the Voronoi cell to which the point belongs.

How to construct Vornoi cells using lifting

Having our terms all sorted out, it becomes apparent what the second definition means. Broadly, it tells us that by drawing edges between the points that generate two neighboring Voronoi cells, we will get a Delaunay Triangulation of the set of points. Observe that the edges we are drawing to geometrically represent the nerve of the Voronoi diagram are always perpendicular to the boundaries of the cells. Just try for a moment to draw a Voronoi diagram that yields triangles with small angles, and you will begin to see why this property maximizes the minimal angle. The only problem would be having more than 4 cells meeting at a point. As it turns out, this is equivalent to four points lying on the same circle, which, as we’ve stated in the first part, makes for having more than one Delaunay Triangulation.

These constructions are less intuitive and you might ask why do we need them when we already have something as simple as the first definition of a Delaunay Triangulation. The reason is that there exist algorithms such as Fortune’s Algorithm or Bowyer-Watson Algorithm that generate Delaunay Triangulations using Voronoi cells. These algorithms prove to be more useful as they can create Vornoi diagrams which have multiple applications across a vast array of domains.

Delaunay Triangulation derived from a Voronoi Diagram

Now that we have a strong theoretical basis, let us focus on one algorithm for creating a Delaunay Triangulation. Note that there are a lot of algorithms for doing this, but the one that we will be presenting is one of the simplest and most time efficient. The algorithm that we choose to implement employs the “divide and conquer” strategy.

Let us start with a set of random points ( we will work with an example that has 12 points to gain a better intuition). We begin by ordering them with respect to their x-coordinate. Also, if two points have the same x-coordinate, their ordering is determined by their y-coordinate in increasing order.

This our example of 12 points with the labeling imposed by our ordering.

We continue by subdividing the points into halves using their labeling, until we are left with sets of two or three points. If we can’t split a set into two equal sets, we let the first subset to have one more element then the second. We then triangulate the newly formed sets by creating triangles in the case where we are left with three vertices, and edges in the case where we are left with two vertices.

The way we divide the set of points and the triangulations we can form. The thickness of the black lines indicates the order in which we divide starting from thickest

By taking a look at the picture, we can observe that we obtain a bunch of triangles with sharp angles which should give us an idea that most of the triangles formed in these first steps are not part of the Delaunay triangulation. However, as we have discussed earlier, the triangles in a Delaunay triangulation tend to be small, so it is very likely that some of the edges coincide. For a large number of vertices, this a huge time saver.

The next step is to merge neighboring sets of points by adding edges in the opposite order in which we have divided them. We will use the following notation to distinguish between edges: LL are edges that were formed using vertices from the left division, RR are edges that were formed using vertices from the right division, and LR are edges that were formed using vertices from both. We will try to now merge the first two divisions. For now we only have LL and RR edges. Throughout the process we will delete LL and RR edges but never add more, and we will try to add LR edges that are as good as possible. Remember that union of the triangles in a Delaunay triangulation of a set of points forms the convex hull of that set of points. Thus, we can safely assume that our first LR edge, which will certainly be in the final triangulation, is the edge between the two points with the smallest y-coordinate of the two divisions. Observe that this is also true for the upper part of the set of points.

Now it’s time to look for the next LR edge that can only be added above the previously created LR. To get a triangulation, we need this edge to start at one of the vertices of the previously added edge. Thus, we are looking for an vertex that forms with the previous LR edge a triangle whose circumcircle does not contain any other points. By the existence of a Delaunay triangulation and by its uniqueness(if we don’t have four co-circular points) we are guaranteed that such a point exists and that it is unique. We will look at the possible candidates and pick the best one from each side and then the best one from the two. Let us start with the right side. We will look at the vertices that share an edge with point 5 and pick the ones that form the two smallest angles with the previously added LR edge. The vertex associated with the smallest angle will be the Current Potential Candidate(CPC) and the other vertex will be the Next Potential Candidate(NPC). If our CPC fullfils the two following criteria we found our candidate for the right side :

• The clockwise angle from the base LR-edge to the potential candidate must be less than 180 degrees. (This ensures that we have traingles and that we don’t go outside the convex hull)
• The circumcircle defined by the two endpoints of the base LR-edge and the potential candidate must not contain the next potential candidate in its interior. (This is the Dealunay criterion that no circumcircle contains a point in its interior)

If our CPC doesn’t fullfill the criteria, we set CPC to NPC and then get the next NPC by looking at the next vertex in order of the angle mentioned above. We repeat this process until we either find a good candidate or we run out of candidates. If we do run out of candidates, the best candidate from the other side will win. If neither side has a candidate, then our merge is complete.

The process for the right side is similar, but instead of point 5 we use point 2 and we measure the angle at point 2 counter-clockwise. If we candidates from both sides, we repeat the circle test and pick the point for which the other point is not in the circumcircle. Be the existence of the Delaunay triangulation, we are guaranteed that such a point exists.

Once we get a “winner” vertex, we delete any vertex that intersects the newly formed LR edge.

We repeat this process until we have completed the merge, then move on through all the merges until our triangulation is complete. Note that any step of the way, we can delete previously added edges, so don’t assume that any of the created LR edges will be part of the final triangulation.

I will display the process for the first merges and then just display the result of the second and third merges:

Vertex 3 and vertex 4 are the candidates from each side, but vertex three obviously wins

We add the new edge and repeat the process

Right side:
We start with 4 but fail the test so 6 is selected.
Left side: we can’t pick 2 because the angle is more than 180, but 1 works.
Of the two candidates 6 wins.

We add the new edge. Note the deletion of the RR edge.

Observe that we have 4 co-circular points, so we can pick either 34 or 16 as our edge

We add the final two edge. The last one doesn’t require any computation.

The finite Delaunay Triangulation of our set of points. A true beauty!

Triangulations seem like an easy mathematical concept, but things get a lot more complicated when you only have simple instructions at your disposal. Next time you want a brain teaser, try to forget everything you have just read, and attempt to create an algorithm that triangulates ( not even a Delaunay Triangulation) the convex hull of a set of points. You will see how things that you can easily do with a pen and a piece of paper become a lot harder to translate into instructions that work for all cases and that a machine can understand. That’s why computer science requires a vast knowldge  of mathematical concepts that are able to describe the same object or process into different modes, allowing the programmer to pick a method that can be transformed efficiently into code.

This entry was posted in Uncategorized. Bookmark the permalink.