Monotone Chain

释义 Definition

Monotone chain（单调链/单调链法）：计算几何中常用的凸包（convex hull）构造方法（也常指“Andrew 单调链算法”）。它通常先按坐标排序点集，然后分别构建下凸包与上凸包，利用叉积判断转向并移除不满足凸性的点，最终合并得到凸包。

发音 Pronunciation (IPA)

/ˈmɒnətoʊn tʃeɪn/

例句 Examples

We used the monotone chain algorithm to compute the convex hull.
我们使用单调链算法来计算凸包。

After sorting the points by x-coordinate (and y as a tie-breaker), the monotone chain builds the lower and upper hulls by repeatedly removing points that create a non-left turn.
在按 x 坐标排序（y 坐标作并列比较）后，单调链通过反复删除造成“非左转”的点来构建下凸包与上凸包。

词源 Etymology

“Monotone”意为“单调的/单向递增或递减的”，在这里指点按坐标排序后，构造凸包边界时呈现出一种按 x（或 y）方向单调推进的特征；“chain”指边界上一段连续连接的点（像链条一样）。因此“monotone chain”直观上就是“沿某个方向单调推进的一条边界链”。

相关词 Related Words

• Convex
• Hull
• Convex Hull
• Polygon
• Vertex
• Edge
• Cross Product
• Orientation
• Graham Scan
• Andrew Algorithm

文学与著作出现 Literary Works

• Computational Geometry: Algorithms and Applications（Mark de Berg 等）：在凸包章节常提到或等价介绍单调链式的凸包构造思路。
• Competitive Programming 3（Steven Halim 等）：在凸包实现部分常以“Monotone Chain / Andrew’s algorithm”名义出现。
• CP Algorithms（在线算法手册，常被引用为“cp-algorithms”）：凸包条目中以“Monotone chain”作为标准实现方法之一。