凸包

Envoltura convexa de un conjunto de 15 puntos en el plano.

The convex hull of the red set is the blue and red convex set.

在一个实数矢量空间 $V$ 中，对于给定集合 $X$ ，所有包含X的凸集的交集 $S$ 被称为 $X$ 的凸包。

$X$ 的凸包可以用 $X$ 内所有点 $(x_1, \ldots, x_n)$ 的线性组合来构造。

在二维欧几里得空间中，凸包可想象为一条刚好包着所有点的橡皮圈。

逐次将点加入，然后检查之前的点是否在新的凸包上。由于每次都要检查所有之前的点，时间复杂度为 $O(n^2)$ 。

首先由一点必定在凸包的点开始，例如最左的一点 $A_1$ 。然后选择 $A_2$ 点使得所有点都在 $A_1A_2$ 的右方，这步骤的时间复杂度是 $O(n)$ ，要比较所有点以 $A_1$ 为原点的极坐标角度。以 $A_2$ 为原点，重复这个步骤，依次找到 $A_3,A_4,...,A_k,A_1$ 。这总共有 $k$ 步。因此，时间复杂度为 $O(kn)$ 。

由最底的一点A_1开始（如果有多个这样的点，那幺选择最左边的），计算它跟其他各点的连接和x轴正向的角度，按小至大将这些点排序，称它们的对应点为 $A_2,A_3,...,A_n$ 。这里的时间复杂度可达 $O(n \log{n})$ 。

单词	Convex hull
释义	Convex hull 中文百科凸包在一个实数矢量空间 $V$ 中，对于给定集合 $X$ ，所有包含X的凸集的交集 $S$ 被称为 $X$ 的凸包。 $X$ 的凸包可以用 $X$ 内所有点 $(x_1, \ldots, x_n)$ 的线性组合来构造。在二维欧几里得空间中，凸包可想象为一条刚好包着所有点的橡皮圈。逐次将点加入，然后检查之前的点是否在新的凸包上。由于每次都要检查所有之前的点，时间复杂度为 $O(n^2)$ 。首先由一点必定在凸包的点开始，例如最左的一点 $A_1$ 。然后选择 $A_2$ 点使得所有点都在 $A_1A_2$ 的右方，这步骤的时间复杂度是 $O(n)$ ，要比较所有点以 $A_1$ 为原点的极坐标角度。以 $A_2$ 为原点，重复这个步骤，依次找到 $A_3,A_4,...,A_k,A_1$ 。这总共有 $k$ 步。因此，时间复杂度为 $O(kn)$ 。由最底的一点A_1开始（如果有多个这样的点，那幺选择最左边的），计算它跟其他各点的连接和x轴正向的角度，按小至大将这些点排序，称它们的对应点为 $A_2,A_3,...,A_n$ 。这里的时间复杂度可达 $O(n \log{n})$ 。英语百科 Convex hull 凸包 In mathematics, the convex hull or convex envelope of a set X of points in the Euclidean plane or Euclidean space is the smallest convex set that contains X. For instance, when X is a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around X.
随便看	Prepyloric septum的意思 prepyloric spasm的意思 prepyloric sphincter的意思 prepyloric ulcer的意思 prepyloric vein的意思 prepyloric veins的意思 Prepylorus的意思 PREPYMT的意思 prepyramid的意思 prepyramidal的意思 prepyramidal fissure的意思 prepyramidal sulci的意思 prepyramidal sulcus的意思 prepyramidal tract的意思 Prepyriform cortex的意思 prepyrogen的意思 preQ的意思 Preqin的意思 preqnancy gingivitis的意思 prequadratic的意思 prequalification的意思 prequalification of prospecitve bidders的意思 prequalifications的意思 prequalification test的意思 prequalify的意思

Convex hull

凸包

Convex hull 凸包