By Kirk Gardner, Kirk E. Jordan, Alex Harrison, James L. McDonagh, Breanndán Ó Conchúir, Thomas J. Peters, and Donald R. Sheehy
While computational topology enjoys considerable contemporary prominence, it is certainly not an overnight success story. The field’s prosperity relies heavily upon classical foundations from general, geometric, algebraic, and low-dimensional topology. Here we explore applications that range from manifolds for airfoils to molecules for pharmaceuticals.
Introduction, History, and Manifolds
The first usage of the term computational topology likely occurred within a 1983 doctoral dissertation on computer aided geometric design (CAGD) [10]. Two decades later, pioneers in topological data analysis (TDA) greatly popularized the term [5, 7]. This article emphasizes geometric topology for analysis of point clouds, suggesting promise for the integration of CAGD and TDA techniques under the broad abstractions of applied topology [8].
Within geometric design, boundary surfaces of solids frequently form from the intersection of two surfaces, which then join along this intersection (see Figure 1a). Practical complications arise, as numerical computations yield deviations from this abstract theory [9]. Researchers often assume that the intersected surfaces are manifolds, so algorithmic detection of self-intersections is an important focus [2]. Figure 1b depicts numerical errors between two manifolds that are joined along their intersection curves [4]. We model the surfaces as splines and compute two pre-images of the intersection curve (one in each surface’s parametric domain); these actions lead to the indicated numerical differences since the curves are instantiated on each surface. Considerations in aeronautical design and engineering for modeling fuselages and wings inspired Figure 1.
Figure 1. Surface intersection for boundary. Figure courtesy of Thomas Peters.
CAGD’s success revolutionized engineering design and manufacturing. Boundary representation (B-rep) models became a dominant approach to topological representations [9, 11], and general topology, combinatorial topology, low-dimensional topology, and knot theory for isotopic equivalence provided supporting ideas [1]. Researchers focused heavily on the adaptation of “pure topology” concepts to finite precision data [9, 11].
Data for Molecules
Here we apply geometric topology to data pertaining to molecules’ point clouds, which we generated from supercomputer simulations of dissipative particle dynamics. This adaptation of computational topology from CAGD to computational chemistry and chemical engineering extends the rich history of topological modeling in chemistry [12]. The corresponding examples are micelles, which are optimized for industrial applications of controlled drug release, household cleaning products, and friction modifiers in vehicle engines [6]. The annotations of Figure 2 distinguish micelles that are “approximately convex” from “worms,” which are the focus of current research.
Figure 2. Approximations of convexity. Figure courtesy of Michael Johnston and Vassilis Vassiliadis.
While convexity is solely a geometric property, extraction of the topological boundary accelerated the algorithmic identifications. This was based upon a heuristic that any point having six or more adjacent points was an interior point (all pairwise Euclidean distances were pre-computed, with unit distance as the upper bound for adjacency since no exterior points existed). The approach typically reduced the data by an order of magnitude, whereas the resulting image is representative of one video frame. This data reduction permitted algorithmic shape identification to run synchronously with the simulation.
In its simplest form, a worm is like a twisted garden hose (see Figure 3). A central axis to approximate the length is of particular interest for chemical analysis. In simplified worms, one can extract such a skeleton with adaptations of the medial axis (MA), which is topologically unstable. Empirical algorithmic refinements attained topological stability for the given data. Piecewise linear approximations to the MA were especially appropriate, as is also often true in CAGD.
Figure 3. Worm. Figure courtesy of Kirk Gardner.
Figure 4 depicts a worm’s additional topological complexities. This worm is a non-convex, simply connected shape, but its skeleton is not homeomorphic to a line segment. Chemists visually identified the thin bridging (near the center of Figure 4) as structurally important.
Figure 4. Bridging and branched skeleton. Figure courtesy of Kirk Gardner.
Researchers developed special purpose algorithms to create responsive branched skeletons. They first computed discrete Laplacians and the Fiedler gap to generate clusters in point clouds [3], then connected the centroids to form an initial piecewise linear (PL) approximation of the skeleton. Further refinements extended line segments to the extreme points of the topological boundaries. Next, scientists calculated the skeleton’s total length as a sum of the lengths of the segments in the PL skeleton, and estimated an average value of the cross-sectional radius around the skeleton. They used these two parameters for computational chemical analyses [6], which strongly corroborated postulated theories about micelles.
Concluding Thoughts
Here we share some of topology’s rich interaction with geometric modeling and design. A similarly robust synergy is simultaneously occurring between topology and data analysis. The former relies more heavily on geometric and differential topology, while the latter depends on algebraic topology. As big data is also a prominent component of design, we invite readers to consider synergy between these two facets of computational topology, as expressed here and in the January/February 2020 issue of SIAM News.
Acknowledgements: Richard L. Anderson, David Bray, Michael A. Johnston, and William Swope also made scientific contributions to this article. Kirk Gardner and Thomas J. Peters gratefully acknowledge generous financial support from IBM Research through its Open Collaborative Research and Shared University Research programs, by award IBM-TJP-6328340. Kirk Gardner and Donald R. Sheehy also appreciatively acknowledge partial funding from National Science Foundation (NSF) grant CCF-1652218. All statements in this article—including any errors—are the sole responsibility of these authors, not IBM Research or the NSF. All of the IBM and Science and Technology Facilities Council (STFC) teams were supported by the STFC Hartree Centre’s “Innovation Return on Research” programme, which is funded by the U.K. Department for Business, Energy and Industrial Strategy.
References
[1] Amenta, N., Peters, T.J., & Russell, A.C. (2003). Computational topology: ambient isotopic approximation of 2-manifolds. Theoret. Comp. Sci., 305, 3-15.
[2] Andersson, L.E., Peters, T.J., & Stewart, N.F. (1998). Selfintersection of composite curves and surfaces. CAGD, 15, 507-527.
[3] Biggs, N. (1993). Algebraic Graph Theory (Vol. 67). New York, NY: Cambridge University Press.
[4] Blackmore, D., & Peters, T.J. (2007). Computational topology. In Open Problems in Topology II (pp. 493-545). New York, NY: Elsevier.
[5] Carlsson, G. (2009). Topology and data. Bull. Amer. Math. Soc., 46(2), 255-308.
[6] Conchuir, B.O., Gardner, K., Jordan, K.E., Bray, D.J., Anderson, R.L., Johnston, M.A., …, Peters, T.J. (2020). An efficient algorithm for topological characterisation of worm-like and branched micelle structures from simulations. J. Chem. Theor. Comput., doi.org/10.1021/acs.jctc.0c00311.
[7] Edelsbrunner, H., & Harer, J. (2010). Computational Topology: An Introduction. Providence, RI: American Mathematical Society.
[8] Ghrist, R.W. (2014). Elementary Applied Topology (Vol. 1). Seattle, WA: CreateSpace Seattle.
[9] Hoffmann, C.M. (1996). How solid is solid modeling? In Workshop on Applied Computational Geometry (pp. 1-8). New York, NY: Springer.
[10] Mäntylä. M. (1983). Computational topology: a study of topological manipulations and interrogations in computer graphics and geometric modeling In Acta Polytechnica Scandinavica. Mathematics and Computer Science Series (No. 37). Helsinki: The Finnish Academy of Technical Sciences.
[11] Patrikalakis, N.M., & Maekawa, T. (2009). Shape Interrogation for Computer Aided Design and Manufacturing. New York, NY: Springer Science & Business Media.
[12] Sumners, D.W. (1990). Untangling DNA. Math. Intellig., 12(3), 71-80.
Kirk Gardner is a doctoral student in computer science at North Carolina State University, under the guidance of Donald R. Sheehy. Kirk E. Jordan is an IBM Distinguished Engineer of Data Centric Solutions, IBM T.J. Watson Research and Chief Science Officer at IBM Research UK, and member of the IBM Academy of Technology. Alex Harrison, James L. McDonagh, and Breanndán Ó Conchúir are research staff at IBM Research. Thomas J. Peters is a professor of computer science and engineering and a professor of mathematics at the University of Connecticut. Donald R. Sheehy is a professor of computer science at North Carolina State University.