凸包

凸包是包含点集的最小凸集公理库凸集Convex set任意两点间线段全部包含在集合中的向量空间子集。，同时包含内部与边界。已经位于凸包内的输入点不会扩大凸包；线性泛函在凸组合上取输入值的加权平均，所以取凸包不改变其上确界，但该上确界未必取得。

关键条件是凸组合系数非负且和为一；若允许负系数但仍要求系数和为一，得到仿射包；若连系数和的约束也取消，得到线性张成。例如单点 $\{(1,0)\}$ 的凸包与仿射包都是自身，而线性张成是整条横轴。橡皮筋只描述有限平面点集凸包的边界，凸包本身还包含内部。

三角形三个顶点的凸包是整个三角形，内部点不改变结果。更具体地，点集 $(0,0),(1,0),(1,1),(0,1),(1/2,1/2)$ 的凸包是单位正方形，中心点不成为顶点，因为它可写成四个角点的凸组合。Graham scan 先按极角排序，再用方向判定维护左转栈，在比较/实数 RAM 模型下给出确定性最坏 $O(n\log n)$；单调链达到同一界。对非空有限输入，若输出极点数为 $h$，输出敏感算法公理库输出敏感分析Output-sensitive analysis · Output-sensitive algorithms在明确输出接口后，同时用输入规模与实际输出规模刻画算法运行成本的分析方法。可以达到 $O(n\log max\{2,h\})$；这也覆盖全部输入点重合、只有一个极点的情形。空输入直接返回空凸包。只报一个输入规模有时会掩盖这种更细的保证。

若所有点共线，凸包退化为两端点之间的线段；只有一个不同点时则退化为单点，而不是二维多边形。边界上其余共线点是否全部输出取决于 API 约定：几何对象的极点只有端点，但某些算法题要求保留所有边界输入点。重复点、浮点近共线和输入顺序也必须显式处理。

凸包适用于任意点集，每个成员由有限公理库有限集Finite set与某个自然数初始段等势、因而能够在有限步内无遗漏编号的集合。凸组合见证。Carathéodory 定理公理库Carathéodory 定理Caratheodory theorem in convex geometry有限维凸包中的每个点都可由至多维数加一个原集合点的凸组合表示。保证，在 ${\mathbb{R}}^d$ 中至多用 $d+1$ 个原始点即可表示任一凸包点。凸包未必闭，例如 $(0,1)$ 的凸包仍是自身；空集的凸包约定为空。以下算法则只讨论有限输入。构造过程常由方向判定公理库方向判定Orientation test用二维或高维行列式符号判断点组转向或仿射定向的基本谓词。驱动 Graham scan 或 monotone chain；共线与重复点要求精确谓词和明确 tie-breaking。随机增量构造公理库随机增量构造randomized incremental construction · RIC按随机排列插入对象，以冲突关系和反向分析控制几何结构的期望构建成本。提供期望分析的另一条路线，但随机排列的期望界不能写成确定性最坏界。数据超出内存时应在外存模型公理库外存 / I/O 模型External-memory model · I/O model · Aggarwal–Vitter model只计大小为 B 的数据块在容量为 M 的内存与外存之间传输次数的两层存储模型。下计块传输，并行实现则按并行模型公理库并行算法模型parallel algorithm model · parallel computation model用总工作、关键路径、处理器数和通信成本共同描述并行算法，而不只报告理想加速比。分别报告工作与深度。

凸包边界上的站点对应Voronoi 图公理库Voronoi 图Voronoi diagram · Voronoi tessellation按到有限站点集中的最近距离把度量空间划分为闭合单元及其公共边界。的无界 cell，Delaunay 三角剖分公理库Delaunay 三角剖分Delaunay triangulation以空外接圆条件或 Voronoi 邻接刻画有限平面点集的几何三角剖分。覆盖同一凸包。对非空有限点集的凸包，线性目标总能在某个极点取得最优；旋转卡壳公理库旋转卡壳与凸多边形直径Rotating calipers diameter algorithm沿凸多边形的支撑方向单调推进对踵点，枚举足够的候选对并在线性时间求出最远距离。还可在极点循环序列上求最远点对。凸多边形 Minkowski 和公理库凸多边形 Minkowski 和的边归并Minkowski sum of convex polygons归并两个凸多边形的边方向构造逐点和，并用反射后的机器人轮廓精确表达平移碰撞禁区。归并两个轮廓的支撑方向，并把反射后的机器人轮廓加到障碍上，用于构造平移碰撞禁区。