幾何設計中的計算拓撲學:流形與分子

作者: Kirk Gardner, Kirk E. Jordan, Alex Harrison, James L. McDonagh, Breanndán Ó Conchúir, Thomas J. Peters, 和 Donald R. Sheehy

儘管計算拓撲學在現代相當的突出, 它的發展與推廣並不是一夕之間發生的. 這個領域能興盛在很大的程度上是仰賴了許多經典的基礎學科包含了一般, 幾何, 代數, 和低維拓撲學. 這裡我們探索計算拓撲學從機翼中的流形到藥物中的分子的運用.

簡介, 歷史, 和流形

計算拓撲學這個詞可能最早出現在一篇1983年有關電腦輔助幾何設計 (CAGD) 的博士論文中[10]. 二十年之後, 拓撲數據分析 (TDA) 的先驅者很大程度地普及了這個詞 [5, 7]. 這一篇文章強調幾何拓撲學在點雲分析中的運用, 暗示著在廣義的應用拓撲學抽象化之中CAGD和TDA的技巧整合可能性 [8].

在幾何設計之中, 固體的邊界面經常是由兩個面交集然後順著交集處做連接所形成 (詳圖1a). 實際施行起來一定會遇到問題, 因為實際數值的計算跟抽象理論會有誤差 [9]. 因為研究員通常把交集的面假設成流形, 用演算法來偵測自我相交就變成一個重要的議題 [2]. 圖1b顯示出順著相交的曲線交合的兩個流形之間的數值誤差 [4]. 我們用平滑曲線來模擬面並計算出交集處曲線的兩個原像 (兩個原像分別在兩個面的參數域裡); 這做法會促成以上提及的數值差異因為曲線是具現化在各個面上的. 在航空設計與工程裡做機身和機翼建模會用到的考量啟發了圖一.

圖一. 面的交集成為邊界. 圖由Thomas Peters提供.

CAGD的成功革新了工程設計和製造. 邊界代表(B-rep)模型成為了一個拓撲代表中的主導做法 [9, 11], 而一般拓撲學,組合拓撲學, 低維拓撲學, 和用在同位相等的紐結理論負責提供輔助性的理念 [1]. 研究員非常地注重”純拓撲學”概念的應用到有限經度數據上 [9, 11].

用於分子的數據

這裡我們把幾何拓撲學套用到分子點雲的相關數據上. 這些數據是我們使用超級計算機模擬耗散粒子動力學所產生出來的. 把計算拓撲學套用到從CAGD到計算化學和化學工程的領域是延續了拓撲建模在化學中長期以來的應用 [12]. 最貼切的例子就是微胞. 微胞在工業運用中是需要被最佳化的, 包含在控釋型藥品,家庭清潔用品,和車輛引擎中摩擦力改良的應用 [6]. 圖二中的註解分辨“大致凸起”和“蟲體”的微胞, 也就是當前研究的焦點.

圖二. 概略凸度. 圖片是由Michael Johnston和Vassilis Vassiliadis提供.

雖然凸度單純的是一個幾何屬性, 拓樸學邊界的萃化促成了演算法的識別. 這是建基於一個假設的原則, 也就是任何一個點若有六個或更多的相鄰點就一定是內點 (每一個成對的歐幾里德距離都預先做好計算且單位距離被設為鄰接的上限值因為外點並不存在). 這樣的做法通常可以成功的把數據做一整個數量級的縮小, 而縮小後的圖像差不多是一個圖像幀的大小. 這樣的數據簡化讓使用演算法的圖形識別可與模擬同步進行.

在最簡化了的型態中, 蟲體就是一個扭曲的園藝軟管 (詳圖三). 在這樣的情況下, 找出中心軸並用中心軸來估計型態長度在化學分析中是特別有益的. 在簡化了的蟲體中, 可以使用中軸(MA)適應來提取這樣的骨架, 雖然MA本身是缺乏拓撲穩定性的. 然而, 透過施行經驗所做出的演算法調整可以帶給數據拓撲穩定性. 以結果而言, 就如同在CAGD中, MA的分段線性估計是特別的合適.

圖三. 蟲體. 圖是由Kirk Gardner提供.

圖四描繪的是蟲體其他拓撲屬性方面複雜的部分. 雖然這蟲體呈現的是一個非凸, 單純連接著的形狀, 他的骨架與線段卻並不同胚. 化學家憑藉著視覺上的觀察來判斷出接近圖四中心的細小橋接在結構上是重要的.

圖四. 橋接和分枝的骨架. 圖是由Kirk Gardner提供.

因此, 研究者發展出特殊用途演算法來建構可以有效做計算的分支骨架. 他們先計算了離散拉普拉斯和費德勒缺口來在點雲之中產生聚集 [3], 接著連接質心來組成骨架的最初分段線性(PL)概算. 進一步的改良延伸線段到拓撲邊界的極值點. 接著, 科學家加總起PL骨架中線段的長度來計算骨架的總長度, 並估計出骨架周圍橫斷面半徑的平均值. 這兩個參數被用來進行計算化學分析 [6]. 如此得出的結果跟與微胞有關的假定理論強烈地互相印證.

結尾省思

我們在這裡分享了一些拓撲學跟幾何建模和設計之間的豐富交流. 相對應的健全協同增效作用也在拓撲學和數據分析之間發展. 前者較依賴幾何和微分拓撲學, 而後者則依賴著代數拓撲學. 大數據也是設計裡一個重要的元素. 我們敬邀讀者深思這計算拓撲學兩個不同面向的協同增效作用, 參考這一篇文章和在2020年1月/2月SIAM新聞期刊中所闡述的內容.

致謝: Richard L. Anderson, David Bray, Michael A. Johnston 和 William Swope 也對這一篇文章做出了科學上的貢獻. Kirk Gardner 和 Thomas J. Peters 很感謝IBM-TJP-6328340獎勵, IBM研究透過開放式合作研究和共有大學研究計畫所提供的豐厚經濟援助. Kirk Gardner 和 Donald R. Sheehy 也很感謝國家科學基金會 (NSF) 補助金 CCF-1652218 所做到的部分資金贊助. 這一篇文章裡的所有聲明 – 包括錯誤 – 由作者們負擔所有的責任, 跟IBM研究和NSF無關. 全部的IBM和科技設施委員會 (STFC) 團隊是由STFC哈特里中心的”創新研究報酬”活動支持, 由英國商業, 能源暨工業策略部做資金提供.

參考文獻

[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). [代數圖論 (第67集).] 紐約市, 紐約州: 劍橋大學出版社.

[4] Blackmore, D., & Peters, T.J. (2007). Computational topology. In Open Problems in Topology II (pp. 493-545). [計算拓撲學. 拓撲學中還未解決的問題 II (pp. 493-545).] 紐約市, 紐約州: 愛思唯爾.

[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. [計算拓撲學: 緒論.] 普羅維登斯縣, 羅得島州: 美國數學學會.

[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). [實體模型法是否夠扎實? 應用計算幾何討論會 (pp. 1-8).] 紐約市, 紐約州: 施普林格.

[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). [數學與電腦科學系列 (37號).] 赫爾辛基: The Finnish Academy of Technical Sciences.

[11] Patrikalakis, N.M., & Maekawa, T. (2009). Shape Interrogation for Computer Aided Design and Manufacturing. [形狀詢問用於電腦輔助設計和製造.] 紐約市, 紐約州: 施普林格科學 & 商業媒體.

[12] Sumners, D.W. (1990). Untangling DNA. [解開 DNA.] Math. Intellig., 12(3), 71-80.

Kirk Gardner是一名北卡羅萊納州立大學電腦科學博士生, 由Donald R. Sheehy所指導. Kirk E. Jordan 是一名IBM傑出數據中心解決方案工程師, 也是英國IBM研究的IBM T.J. Watson 研究和首席科學官, 並是IBM技術學院的成員. Alex Harrison, James L. McDonagh, 和 Breanndán Ó Conchúir 是在IBM研究的研究人員. Thomas J. Peters 是在康乃狄克大學的計算科學和數學教授. Donald R. Sheehy是北卡羅萊納州立大學的電腦科學教授.