From triangles to computer graphics

 In AMSI in the news, News

Opinion piece by Winter School lecturers Joan Licata and Anthony Licata.

What does connect-the-dots have to do with watching a Pixar film? More than you might think.

A connect-the-dots page starts with nothing but some labelled points. As each dot is joined to the next, however, a picture emerges. Each step is simple — just add a line segment between two points — but the resulting image can be extremely complex.

Toddlers can produce masterpieces this way, but so can computers. When a computer needs to draw a curve, it starts by connecting a sequence of points. Using just a few points might result in a zigzag with sharp corners, but increasing the initial number of points makes the resulting curve look smoother. With enough points and line segments, we can approximate even the most complicated curves.

Dots lines and curves

But maybe you’re more ambitious. Suppose you’re not interested in drawing curves, but rather, in constructing two-dimensional surfaces. Can you use an analogous approach to build a plane or a sphere or something more elaborate?

Triangles — the simplest two-dimensional objects — serve as building blocks for more complicated surfaces. Just as we can connect a pair of points with a line segment, we can connect three points via a triangle. And, just as we can make complicated curves by gluing lots of segments at their endpoints, we can make complicated surfaces by gluing lots of triangles along their edges. We can approximate extremely complex surfaces as long as we use enough triangles.

Mathematicians started thinking seriously about constructing surfaces from triangles in the late 19th century, hoping to classify surfaces. In particular, they wanted to understand when two surfaces could be deformed to look the same without cutting or gluing. They developed mathematical tools to study this question, and a century later, it became clear that they’d also laid the groundwork for an important technique in computer graphics.

Imagine trying to model moving cloth, perhaps a flag flapping in the breeze. Since the flag changes shape as it moves through space, this is a much more difficult problem than simulating the movement of a rigid object like a table. If the flag is approximated by triangles, however, modelling it becomes possible because the computer only needs to keep track of sets of three points. When the points move, they carry the triangles with them.

Abstract? Applied? Both!

Mathematicians certainly weren’t thinking about computer graphics in the 1890s. They were studying abstract questions about two-dimensional geometry and developing beautiful mathematics. Nevertheless, the techniques they invented in order to state this question precisely and then answer it have turned out to be extremely useful. In fact, this theme recurs throughout human history: mathematics developed to solve abstract problems turns out to be useful. Maybe not always and definitely not quickly, but it happens over and over again.

The first mathematical objects most people meet are the counting numbers 1, 2, 3… Most counting numbers are formed by multiplying smaller numbers, but not all of them. Some numbers have only 1 and themselves as factors, and these are known as prime numbers. For example, the numbers 2, 3 and 5 are prime, but 4 = 2 x 2 is not.

Prime numbers act as building blocks for the entire number system. Centuries ago, the mathematicians who studied primes didn’t think their efforts would defend a castle or build a better steam engine, but they were intrigued by the search for structure and patterns.

Some of the questions they posed continue to capture the mathematical imagination; today, the most famous unsolved problem in mathematics is the Riemann Hypothesis, which addresses how the primes are distributed among the counting numbers.

Pondering prime numbers might seem like an intellectual game that’s divorced from ‘real world’ concerns. But suppose you ask yourself, ‘Why is it safe to use my credit card to buy something online?’ (Or, maybe better: ‘Is it safe to use my credit card online?’) In fact, the basic techniques for sending data securely over the internet rely on what’s known about factoring a number into primes. Every time you enter your credit card number on a website and hit ‘send’, you have a number theorist to thank.

Likewise, Persian mathematicians began developing the subject we now call algebra in the Middle Ages. This field evolved over centuries, and today, it underpins the algorithms for internet search and Netflix recommendations.

Fourier analysis, which was developed as part of calculus in the late 1700s, provides the basic mathematical tools for signal processing in telecommunications and medical imaging.

Algebraic topology — a branch of mathematics that wasn’t even created until the 20th century — is being used in the 21st century to study artificial intelligence and cancer genomics.

The list goes on, but the striking thing in all these examples is that the original researchers couldn’t anticipate which applied questions would require their work. Plenty of important mathematics is specifically developed to solve real-world problems, but curiosity-driven research is as important today as it ever has been.

But back to triangles

New applications for old mathematics are exciting, but progress also comes in the form of new mathematics.

Computer graphics uses flat triangles to approximate smooth surfaces, but if you’re willing to allow triangles to bend a bit, then you can build any surface by gluing enough of them together. This is equivalent to saying that you can cut any surface into curved triangular pieces.

Sphere made of curved triangles

These curved triangles are an important tool for generalising what we know about geometry to higher dimensions – after all, mathematicians, scientists, and engineers don’t care only about surfaces.

Higher-dimensional spaces occur not only in pure mathematics, but also in nature as patterns in large data sets, as relationships between physical quantities, and in descriptions of the universe itself.

Mathematicians develop formal techniques to study them, compensating for the fact that a seven-dimensional space is harder to picture than a flag. Luckily, the idea of gluing triangles generalises to any dimension! In three dimensions, for example, the analogue of a triangle is a tetrahedron, and just as gluing triangles together builds surfaces, gluing tetrahedra together builds new three-dimensional objects. In higher dimensions, the analogue of a triangle is called an n-simplex, and gluing n-simplices together builds n-dimensional objects.

Tetrahedrons make up 3D objects

Since any surface can be cut into curved triangles, and it’s reasonable to ask if the analogous fact holds in higher dimensions: can any n-dimensional space be cut into n-simplices?

Mathematicians initially speculated that the phenomena they’d observed in dimensions one and two would generalise to all dimensions. This belief came to be known as the Triangulation Conjecture.

Decades of research failed to deliver a proof. Then, breakthroughs in the 1980s revealed examples of four-dimensional objects which can’t be cut into 4-simplices. But in 2012, the Triangulation Conjecture was finally proved false for all dimensions greater than four. The mathematical universe has some very strange shapes!

Disproving the Triangulation Conjecture is a triumph of curiosity-driven research, and the truth now sits on humanity’s bookshelf. It may rest there quietly. Then again, maybe some 26-dimensional space with no triangulations will lead to a cure for cancer.

You never know.

Read the original article on ABC Science

Recommended Posts