# The Geometric Viewpoint

geometric and topological excursions by and for undergraduates

• ## History of Hyperbolic Geometry

Sami was a student in the Fall 2016 course “Geometry of Surfaces” taught by Scott Taylor at Colby College. The essay has been lightly edited before being published here.

Introduction
This essay is an introduction to the history of hyperbolic geometry. Euclid, Gauss, Felix Klein and Henri Poincare all made major contribution to the field. We will discuss some of their influences in the following sections, starting with Euclid and his postulates that defined geometry. Then we will look at the effect of Gauss’s thoughts on Euclid’s parallel postulate through noneuclidean geometry. Later, Klein settled any doubt of noneuclidean consistency. Lastly, Poincare makes some notable contributions to solidifying hyperbolic geometry as an area of academic study.

Euclid’s Postulates
Euclidean geometry came from Euclid’s five postulates. It is the most intuitive geometry in that it is the way humans naturally think about the world. Nonetheless, there are a few other lesser-known, but equally important, geometries that also have many applications in the world and the universe. These “other” geometries come from Euclid’s fifth postulate: “If a straight line falling on two straight lines makes the interior angles on the same side less than two right angles the two straight lines if produced indefinitely meet on that side on which the angles [are] less than two right angles” [6]. See Figure 1(A) below for an illustration of this. An equivalent way to express this is that the angle sum of a triangle is two right angles.

This is also called the parallel postulate because it is equivalent to the following statement: “if one draws a straight line and a point not on that line, there is only one unique line that is parallel to given line through the point” [10]. See Figure 1(B) below.

Figure 1: Visualization of parallel postulate.

Unlike the other postulates, the fifth is not obvious (to satisfy your curiosity, the rest of Euclid’s postulates are attached at the end of this essay). For centuries, mathematicians and amateurs alike attempted to prove that the fifth postulate is a consequence of the first four postulates and other established theorems [6]. However, it turns out this postulate determines whether we are in euclidean or noneuclidean geometry [10].

The Birth of Hyperbolic Geometry
Over 2,000 years after Euclid, three mathematicians finally answered the question of the parallel postulate. Carl F. Gauss, Janos Bolyai, and N.I. Lobachevsky are considered the fathers of hyperbolic geometry. Gauss published little of his work on it because he, allegedly, feared disrespecting Euclid by disproving the parallel postulate. Yet, Gauss extended geometry to include what he coined “non-euclidean,” or the contradiction of the parallel postulate [5]. Bolyai and Lobachevsky published their works on noneuclidean geometry independently but around the same time; however, their findings were not popularized until after 1862, when Gauss’s private letter to Schumacher about his “meditations” on hyperbolic geometry was published. With the work of these three mathematicians, the controversy of the parallel postulate was put to rest. It was definitive that without the parallel postulate, the remaining four postulates created a geometry that is equally consistent [10].

What is hyperbolic geometry?
Now that a brief history of the sources of hyperbolic geometry has been provided, we will define hyperbolic geometry. It has constant negative Gaussian curvature, which resembles a hyperboloid (See Figure 2). Note, that spherical geometry has constant positive curvature [10].

Figure 2: A visualization of Gaussian curvature [8].

First, we will give a few different ways to visualize hyperbolic geometry, then we will explain how to measure distance in this space.

Visualization of Hyperbolic Geometry
A more natural way to think about hyperbolic geometry is through a crochet model as shown in Figure 3 below. This discovery by Daina Taimina in 1997 was a huge breakthrough for helping people understand hyperbolic geometry when she crocheted the hyperbolic plane. This was important because now people can touch and move the crocheted object to get a more intuitive understanding of what a straight line in hyperbolic space would look like.

Figure 3: A crochet from Daina Taimina [3]. You can clearly see that the parallel postulate does not hold here because there are three lines that go through a point and none of them intersect with the given line on the bottom.

As mentioned before, we can visualize hyperbolic geometry through crochet. However, there are some different models including the upper-half plane and the Poincare disk model. See Figure 4 below. The upper-half plane model has the real line as the axis, which we may approach but will never reach. The disk model has the same idea as we approach the edge of the circle. Lines that appear to hit these ideal boundaries at the same point have an angle of 0 between them.

Figure 4

Definition of Distance
Although it may be a bit surprising at first, the definition of metric, or measure of distance, is different for each type of geometry. In Euclidean geometry, the distance is given as

$d_{euc}= \sqrt{(x_1-x_0)^2+(y_1-y_0)^2}$

between two points $(x_0,y_0)$ and $(x_1,y_1)$. Note that in euclidean geometry, the shortest distance between two points is a line (as postulated by Euclid). However, in hyperbolic space, the shortest distance between two points is the arc from point $a$ to point $b$ that lie on the unique semicircle centered at a point on the boundary as shown in Figure 5; if we parameterize the arc as $t \mapsto (x(t),y(t)), \ \ a\leq t \leq b$,

$l_{hyp} = \int_{a}^{b} \frac{\sqrt{x'(t)^2+y'(t)^2}}{y(t)} dt$

See [2].

Figure 5: Hyperbolic geodesic pictured as a euclidean semi-circle centered at a point on x.

Now that we’ve gone over the founding of hyperbolic geometry and have some sense of what it is, we’ll talk about two more influential mathematicians in the field: Felix Klein and Henri Poincare.

Felix Klein
Klein’s contribution to geometry is not only the famous Klein Bottle, but also his proof of the extension of the Cayley Measure on projective geometry to non-euclidean geometry. According to John Stillwell’s translation of On so-called Noneuclidean Geometry, Klein started by showing that each non-euclidean geometry is a special case of projective geometry; he then ended by concluding that non-euclidean geometry can be derived from projective geometry. Furthermore, projective geometry is independent from the theory of parallels; if not, the consistency of projective geometry would be questioned.

Projective Geometry

Projective geometry has simple origins from Renaissance artists who portrayed the rim of a cup as an ellipse in their paintings to show perspective. Projective geometry can be thought of in this way:

The theory of perspective regards the artist’s canvas as a transparent screen through which he looks from a fixed vantage point at the scene he is painting. Light rays coming from each point of the scene are imagined to enter his eye, and the totality of these lines is called a projection. [11]

From there, the idea eventually entered the academic mathematical community where it was incorporated into the study of linear algebra and other areas of mathematics. Projective geometry is the study of invariants on projections – properties of figures which are not modified in the process of projection [11]. Projective geometry is more more general than both euclidean and hyperbolic geometries and this is what Klein uses to show that noneuclidean geometries are consistent.

Figure 6: From the world to the canvas through the artist’s eye. Image found here.

Euclidean and hyperbolic geometry follows from projective geometry

Klein gives a general method of constructing length and angles in projective geometry, which he believed to be the fundamental concept of geometry. To borrow psychology terms, Klein’s approach is a top-down way to look at non-euclidean geometry while the upper-half plane, disk model and other models would be referred to as bottom-up methods. The bottom-up methods are easier to visualize and to deal with applications of hyperbolic geometry. This is remarkable because this top-down approach provides a “more comprehensive” [10] proof than those that had in a case by case manner. Moreover, projective geometry is consistent outside of geometry [10].

Distance in general
The different geometries we get from projective geometry come from the the projection of the fundamental conic. This idea is illustrated below in Figure 7.

Figure 7: Conic Sections

First, Klein defines the general distance function as

$2ic \text{ arccos }\frac{\Omega_{xy}}{\sqrt{\Omega_{xx} \Omega_{yy}}}$
where the constant $c$ determines which space we are in (Hyperbolic, parabolic, elliptic) and

$\begin{array}{rcl}\Omega_{xx} &=& ax_1 ^2+bx_1x_2+cx_2 ^2\\ \Omega_{yy} &=& ay_1 ^2+by_1y_2+cy_2 ^2 \ \text{and} \\ \Omega_{xy} &=& ax_1y_1+b(x_1y_2+y_1x_2)+cx_2y_2 \end{array}$
with $(x_1,x_2) \text{ and } (y_1,y_2)$ as the coordinates of two points.

Klein shows that the fundamental conic section “corresponds completely with the idea of hyperbolic geometry.” Now, the fundamental conic is the projection onto the plane with the appropriate metric; it “determines a measure on all basic figures of the first kind in the plane”[10]. Here, the “first kind” is fuchsian groups [2], which are isometries of the hyperbolic plane. An isometry is a way of transforming a figure in a given space without changing its angles or lengths. Every isometry in hyperbolic space can be written as a linear fractional transformation in the following form:

$\phi(z) = \frac{az+b}{cz+d}$

where $z$ is the complex coordinate of a point. You can think of a complex coordinate in the same way that you think about $(x,y)$ on the euclidean plane where $z = x +\text{i}y$. The “basic figures” are the triangle, circle, and the square. So these isometries take triangles to triangles, circles to circles and squares to squares.

The fundamental conic that forms hyperbolic geometry is proper and real – but “we shall never reach the fundamental conic, let alone pass beyond it”[10]. Recall, our visualizations of hyperbolic space using the upper-half plane model from Figure 4(A), then the fundamental conic is the real line and the fuchsian groups are the isometries acting on $\mathbb{H}^2$.

By using projective geometry to construct noneuclidean geometries, Klein has created a proof that is indisputable.

Henri Poincare
A discussion of the history of hyperbolic geometry cannot leave out Henri Poincare after which the Poincare disk model is named (See Figure 4 (B)). Originally, he began his studies in differential equations, then stumbled upon hyperbolic geometry naturally in his work. He wrote in his book Science and Methods that:

The incidents of travel made me forget my mathematical work. When we arrived at Countances, we got into a break to go for a drive, and, just as I put my foot on the step, the idea came to me, though nothing in my former thoughts seemed to have prepared me for it, that the transformations I had used to define Fuchsian functions were identical with those of non-euclidean geometry. [9]

In fact, he was studying the differential equation $x''(t)+p(t)x(t)=0$ for a given function $p(t)$ that resembles linear fractional transformations with real coefficients. When perturbed to have slightly complex coefficients, this yielded a group $\Gamma$ of linear fractional maps with complex coefficients that act on the Riemann Sphere. This is also related to chaos! He called the ones with real coefficients fuchsian groups after Fuchs and the ones with complex coefficients kleinian groups, though neither Fuchs nor Klein had much to do with the groups they are named after. Allegedly, Klein was offended when Poincare declared the fuchsian group, claiming it had been he, not Fuchs, who had thought about it. So to appease Klein, Poincare named the next group after him. Nonetheless, these are groups of isometries on the hyperbolic plane, $\mathbb{H}^2$ [2].

There have been many other theorems (and still more though current research) in hyperbolic space but these have been instrumental in the creation of hyperbolic geometry. Despite its turbulent history surrounding the parallel postulate and its late debut in the mathematical world, hyperbolic geometry is gaining prominence and has many great applications to the real world.

Euclid’s Postulates [7]:

1. A straight line segment can be drawn joining any two points.
2. Any straight line segment can be extended indefinitely in a straight line.
3. Given any straight lines segment, a circle can be drawn having the segment as radius and one endpoint as center.
4. All Right Angles are congruent.
5. If two lines are drawn which intersect a third in such a way that the sum of the inner angles on one side is less than two Right Angles, then the two lines inevitably must intersect each other on that side if extended far enough.

References:

[1] Antonick, Gary. “The Non-Euclidean Geometry of Whales.” The New York Times. The New York Times, 08 Oct. 2012. Web. 04 Dec. 2016.
[2] Bonahon, Francis. Low-dimensional Geometry: From Euclidean Surfaces to Hyperbolic Knots. Providence, RI: American Mathematical Society, 2009. Print.
[3] Creates, Cris. “Crochet Mathematics: Hyperbolic Crochet.” Crochet Mathematics: Hyperbolic Crochet. N.p., 12 Jan. 2012. Web. 04 Dec. 2016.
[4] “Daina Taimina.” Daina Taimina | Crochet Coral Reef. N.p., n.d. Web. 04 Dec. 2016.
[5] Henderson, David W. Experiencing Geometry: In Euclidean, Spherical, and Hyperbolic Spaces. Contributer: Daina Taimina. 2nd ed. Upper Saddle River, NJ: Prentice Hall, 2001. Print.
[6] Lewis, Florence P. “History of the Parallel Postulate.” The American Mathematical Monthly, vol. 27, no. 1, 1920, pp. 16–23. www.jstor.org/stable/2973238.
[7] McMullen, Curtis T. “Euclid’s Postulates.” Euclid’s Postulates. Harvard University, 1997. Web. 07 Dec. 2016.
[8] Nicoguaro. Gaussian Curvature. Digital image. Wikicommons, 9 Jan. 2016. Web. 6 Dec. 2016.
[9] Poincaré, Henri. Science and Methods. Trans. Francis Maitland. London: T Nelson, 1914. Archive.org.
[10] Stillwell, John. “Introduction and Translation to Klein’s On the So-called Noneuclidean Geometry.” Sources of Hyperbolic Geometry. Vol. 10. Providence, RI: American Mathematical Society, 1996. 63-111. Print. History of Mathematics.
[11] Wylie, C. R. “Introduction to Projective Geometry.” Google Books. Courier Corporation, 2011. Web. 08 Dec. 2016.

This entry was posted in Hyperbolic Geometry and tagged , , . 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.