The cut-away view of a triangulated molecular skin surface of a small molecule with characteristic tunnel in its middle. The surface is without kinks and creases, which allows for the high quality triangulation shown on the left. An alternative rendering of the smooth surface is shown on the right.
The shape of things to come in computational geometry Austrian award-winning scientist, Herbert Edelsbrunner, a pioneer of alpha shapes and persistent homology, is taking these ground-breaking ideas in computational geometry, to empower new applications such as cancer detection and modelling, in the ALPHA project. We are now accustomed to convincing imagery created by three-dimensional geometric modelling software used with computers in a multitude of industries. They help us design engines, create products, plan house builds, model invisible processes such as in microenvironments in nature, and to even create convincing computer-generated images (CGI) in Hollywood movies. However, this world-changing technology is only a few decades old, and its early development came in part from the mathematical imaginings of Herbert Edelsbrunner and his alpha shapes concept, first proposed in 1983, along with his colleagues, David Kirkpatrick & Raimund Seidel. In the field of mathematics, alpha shapes were devised to define a shape around a set of points in the Euclidean plane, reliant on using the radii of circles around the points as a guide to finding form, where they intersect with each other. Alpha shapes began as a way of determining two-dimensional shapes from a set of data points but much later, in the 90s, Edelsbrunner progressed the methodology to construct shapes in three dimensions, with a polygon boundary. It was a major leap in the potential of alpha shapes for practical applications. In this period of the 1990s, the principles of alpha shapes led to a wrap algorithm for surface reconstruction. This proved highly useful for real-world applications in engineering, manufacturing, dentistry, and medicine, to name a few. “When 2D alpha shapes appeared, people attempted to implement 3D but it didn’t really work because the numerical error propagates and it spoils the construction. At other times it would give you a wrong result,” explained www.euresearcher.com
Edelsbrunner, when pondering the early challenges that they faced with the transition to 3D. “Then we developed this method called SOS, which stands for Simulation of Simplicity. This is a very important technique because it allows you to do exact computations and only with this is it possible to correctly implement three-dimensional Delaunay triangulations. When that happened, we used the 3D alpha shapes to see how far we could push their implementation, using Simulation of Simplicity. And that’s how we generated this avalanche of different uses and applications on the computation side.”
called persistent homology (PH) useful for topological algorithms and data analysis. Persistent homology finds the essential features by looking at the ones that exist over a range of scales. This method assesses the scale level and reports noise as lowpersistent features. The user of the result may decide to ignore noise by ignoring these low-persistence features, to form a clearer picture. In effect, these concepts by Edelsbrunner were forming a suite of geometrical calculations that in turn were inadvertently creating a new industry in computational modelling.
What we focused on is this multichromatic data and a starting point was in cancer research. It turns out that the location and the relevant distribution of different types of cells are important when looking at cancer. Computational order from chaos
Shaping industrial applications
This way of making three-dimensional data into three-dimensional shapes has countless real-world practical applications. “In the early 90s we had the software for alpha shapes, which nobody else had, so we could create these beautiful 3D objects, and we were wondering what we could do with this,” recalls Edelsbrunner. “With one development, we showed it to biochemists, who were working on proteins and they noticed a similarity with protein structures. If you take the protein data, the location of the atoms of the protein as input, then we can construct the protein.” Another milestone for Edelsbrunner was the development of a mathematical tool
“It was very lucky because all of a sudden, we could compute things that no one could compute before because they didn’t have the sophistication in geometry or in computation.” Edelsbrunner’s alpha shapes had advanced technological capabilities. He was one of only three computer scientists to win the National Science Foundation’s Alan T Waterman Award and his ideas were a catalyst for co-founding his own business, Raindrop Geomagic, which creates shape modelling software. The often-cited golden goal for investors and innovation, of turning academic breakthroughs into commercial success, was happening on
53