Andrew Algorithm

释义 Definition

Andrew algorithm（Andrew 算法）：一种用于计算平面点集凸包（convex hull）的经典算法，常被称为 Andrew’s monotone chain algorithm（单调链法）。其核心做法通常是先按坐标排序，再分别构建“下凸壳”和“上凸壳”，利用叉积判断转向来剔除不在凸包上的点。（在计算几何与竞赛编程中很常见）

发音 Pronunciation (IPA)

/ˈæn.druː ˈæl.ɡəˌrɪð.əm/

词源 Etymology

“Andrew algorithm”通常指以 Andrew 命名的凸包算法（即 Andrew’s monotone chain）。其中 algorithm 源自中世纪拉丁语 algorismus，进一步追溯到波斯数学家 al-Khwārizmī（花剌子密）姓名的拉丁化形式，后来演变为“算法”的通用词。

例句 Examples

Andrew algorithm computes the convex hull efficiently.
Andrew 算法可以高效地计算凸包。

After sorting the points by x and y, we used Andrew algorithm to build the lower and upper hulls, removing non-left turns with cross products to handle collinear points consistently.
在按 x、y 坐标对点排序后，我们用 Andrew 算法构建下凸壳与上凸壳，并用叉积剔除不符合左转条件的点，从而一致地处理共线点。

相关词 Related Words

• Convex Hull
• Monotone Chain
• Graham Scan
• Computational Geometry
• Cross Product
• Orientation
• Polygon
• Sorting

文学与著作中的出现 Literary Works

• Computational Geometry: Algorithms and Applications（Mark de Berg 等）：凸包章节常介绍多种方法，教学与综述中经常提及单调链（Andrew）这一类实现思路。
• Competitive Programming（Steven Halim, Felix Halim）：竞赛几何部分常以“Andrew’s monotone chain”作为凸包的标准实现之一。
• Programming Challenges（Steven S. Skiena, Miguel A. Revilla）：与竞赛题解相关的几何主题中常出现凸包算法的讨论与实现，包括单调链思路。