從證明到計算
在這道階梯上至今為止，幾何一直是你拿來推理的東西：你證明兩個三角形全等、你把圓錐曲線分類、你動手算出一個曲率。計算幾何問的是另一種問題。給電腦交來成千上萬甚至上百萬個點，到底有什麼實際的 程序——一份機器能執行、由有限步驟組成的食譜——能產出幾何答案，而當輸入變大時這份食譜會變得多慢？這些形狀就是你早已認識的形狀；新鮮的是，我們如今在意的是「找出它們的代價」。
本級的第二篇建立起凸性與 多胞形 的語言——那種「任兩個成員之間的線段都留在內部」的集合，以及多邊形在更高維度的表親。我們在這裡直接倚靠它。我們要計算的第一個對象，完全活在那個世界裡：給一團有限的點，它的 凸包 就是包含全部這些點的最小 凸集。把這些點想成釘進木板的釘子，再套一條橡皮筋繞過外圈；當它鬆開繃緊時，所描出的那個緊繃多邊形就是凸包。有些釘子落在邊界上（成為角點），其餘的則無害地待在內部。
計算凸包
在平面上你究竟要如何找出凸包？最直觀的方法是 禮物包裝法（gift-wrapping）。從一個你確定是角點的點出發——比方說最低的那個。從那裡掃出一條射線，找出下一個點，使得通過這兩點的直線把其餘所有點都留在同一側；那條線就是一條 支撐線，碰著點雲卻不切入其中。轉到那個新點再重複，把一條線繩緊緊纏過外圈，直到回到起點。這正是你親手綑一個包裹的方式。
禮物包裝法很誠實，卻可能慢：若凸包有 h 個角點，它的代價約為 O(n h)，而當幾乎每個點都是角點時，便退化趨向 O(n^2)。一份更聰明的食譜——葛拉漢掃描法（Graham scan）——做得更好。先把這些點按它們相對於一個固定底點所成的角度排序，接著一次走過它們，每一步只對最後三個點問一個問題：它們是左轉還是右轉？左轉就保留新點；右轉就表示中間那點是假角點，於是把它彈掉再重新檢查。每個點至多被壓入與彈出一次，所以排序之後那趟行走是線性的——排序主宰一切，給出著名的 O(n log n)。
The single test at the heart of Graham scan.
For three points A, B, C taken in order, look at
the cross product of AB and BC:
cross = (B - A) x (C - B)
= (Bx-Ax)(Cy-By) - (By-Ay)(Cx-Bx)
cross > 0 : left turn (keep B, it is a real corner so far)
cross < 0 : right turn (B was a false corner; pop it)
cross = 0 : the three points are collinear (a tie to handle carefully)
No angles, no square roots -- just one signed area.切分平面：沃羅諾伊圖
現在來看第二個感覺截然不同的問題。把一把點撒在平面上——稱它們為 站點（sites），或許是城裡的郵局。對城裡的每一個位置，哪一間郵局最近？把每個位置依答案上色，這些顏色便以相連的色塊填滿平面：一個站點一塊領地，亦即以該站點為最近者的所有地方所成的集合。這個分割就是 沃羅諾伊圖，它是整個幾何學中最低調卻無所不在的結構之一，從手機訊號覆蓋到生物細胞的堆疊都見得到它。
這些邊界並不神秘——你可以直接從這道階梯早期學過的東西把它們讀出來。只考慮兩個站點 P 與 Q。一個點到兩者等距，恰恰就在它落於線段 PQ 的 垂直平分線 上之時。在那條線的一側 P 較近，在另一側 Q 較近。所以只有兩個站點時，平面便沿著它們的垂直平分線乾淨地裂成兩個半平面。一張完整沃羅諾伊圖裡的每一道牆，都是某兩個相鄰站點之間垂直平分線的一段；每一個三牆交會的角點，都是同時到三個站點等距的點。
每一塊領地本身都是一個凸區域——是一些半平面的交集，正是凸性那一篇為你預備好的那種對象。這張圖能算得驚人地快：一種稱為 Fortune 演算法的優雅掃描技巧，能以 O(n log n) 建出整張圖，與排序同樣的代價。一個小小的誠實提醒：這張圖活在尋常平坦的歐氏距離裡。一旦改變「最近」的意涵——改成沿街道的行車時間，或彎曲表面上的距離——這些牆便彎成曲線，而那幅乾淨的垂直平分線圖像就只是起點，而非定論。
同一硬幣的兩面：德勞內
故事在這裡轉為優美。拿你的沃羅諾伊圖，只做一件事：每當兩個站點共用一道牆——也就是它們的領地相鄰——便畫一條線段把這兩個站點連起來。你得到的這張線段網，就是 德勞內三角剖分。它把站點的凸包切成一個個三角形，而它正是沃羅諾伊圖精確的幾何 對偶：沃羅諾伊的角點變成德勞內的三角形，沃羅諾伊的牆變成德勞內的邊。這兩張圖承載著完全相同的資訊，只是穿著相反的衣裳——一張是分成區域的分割，另一張是三角形的網絡。
在把一個點集切成三角形的眾多方式裡，為何偏要珍視這一種 三角剖分？因為它是最「公道」的一種。德勞內三角剖分具有 空圓性質：對其中每一個三角形，通過該三角形三頂點所畫的圓，內部都不含任何其他站點。一個等價的說法是，在所有可能的三角剖分中，德勞內把最小的角盡量放大——它避開又瘦又細的薄片三角形，偏好肥厚、形狀良好的三角形。當你為工程模擬把一個形狀網格化，或把一張平滑曲面覆蓋在散落的地形資料上時，這正是你要的。
The dual dictionary (sites in the plane, no four on a common circle): VORONOI <--> DELAUNAY --------------------- --------------------- one site <--> one vertex wall between two sites <--> edge joining the two sites corner of three walls <--> triangle on three sites region around a site <--> the triangles touching that vertex Empty-circle test for a candidate triangle: its circumscribed circle must contain no other site inside.
升維、極限與走向何方
這些想法並不困守於平面，而它們向上攀升的方式著實令人驚訝。把你平面上的點，每一個都筆直地抬到一個拋物面上——把點 (x, y) 送到三維中的高度 x^2 + y^2。接著計算這些被抬升的點在空間中的 凸包，只看它的底面。把那個下凸包投影回平面，你得到的恰恰就是德勞內三角剖分。平面上的空圓性質，在高一維處變成了「這個面在凸包底部」這句樸素的陳述。兩個看似毫無關係的問題，原來只是同一個問題的不同偽裝。
不過，要對極限保持誠實。在平面與三維中，這些結構既便宜又友善。但 n 個點在 d 維中的凸包，其面數可以像 n 的 d 次方那樣增長——隨著維度上升，它在組合上可能爆炸。所以「直接跑演算法」在高維度裡就不再是好建議，這正是著名的 維數詛咒（curse of dimensionality）的一個面向。在地圖上微不足道的最近鄰與凸包問題，到了現代資料所棲身的上百維空間裡會變得真正困難，而當前許多研究談的是巧妙的近似，而非精確的答案。
退一步，看看這整篇裡發生了什麼。凸包是上一篇的 多胞形，如今成了機器能造出來的東西；沃羅諾伊圖由你在階梯起步處認識的 垂直平分線 編織而成；連接兩者的橋樑，是向量那一級的 外積。計算幾何並未發明新的形狀——它拿起你早已理解的形狀，以工程般的嚴肅追問：要如何又快又正確地找出它們。這種「古老幾何」與「誠實的代價計算」的揉合，正是本級要帶你看見的現代前沿，而下一篇將把這個故事帶進碎形那奇異的世界。