首页 >
凸包
✍ dations ◷ 2025-07-13 15:10:43 #凸包
在一个实数向量空间
V
{displaystyle V}
中,对于给定集合
X
{displaystyle X}
,所有包含X的凸集的交集
S
{displaystyle S}
被称为
X
{displaystyle X}
的凸包。X
{displaystyle X}
的凸包可以用
X
{displaystyle X}
内所有点
(
x
1
,
…
,
x
n
)
{displaystyle (x_{1},ldots ,x_{n})}
的线性组合来构造。在二维欧几里得空间中,凸包可想象为一条刚好包着所有点的橡皮圈。逐次将点加入,然后检查之前的点是否在新的凸包上。由于每次都要检查所有之前的点,时间复杂度为
O
(
n
2
)
{displaystyle O(n^{2})}
。首先由一点必定在凸包的点开始,例如最左的一点
A
1
{displaystyle A_{1}}
。然后选择
A
2
{displaystyle A_{2}}
点使得所有点都在
A
1
A
2
{displaystyle A_{1}A_{2}}
的右方,这步骤的时间复杂度是
O
(
n
)
{displaystyle O(n)}
,要比较所有点以
A
1
{displaystyle A_{1}}
为原点的极坐标角度。以
A
2
{displaystyle A_{2}}
为原点,重复这个步骤,依次找到
A
3
,
A
4
,
.
.
.
,
A
k
,
A
1
{displaystyle A_{3},A_{4},...,A_{k},A_{1}}
。这总共有
k
{displaystyle k}
步。因此,时间复杂度为
O
(
k
n
)
{displaystyle O(kn)}
。由最底的一点
A
1
{displaystyle A_{1}}
开始(如果有多个这样的点,那么选择最左边的),计算它跟其他各点的连线和x轴正向的角度,按小至大将这些点排序,称它们的对应点为
A
2
,
A
3
,
.
.
.
,
A
n
{displaystyle A_{2},A_{3},...,A_{n}}
。这里的时间复杂度可达
O
(
n
log
n
)
{displaystyle O(nlog {n})}
。考虑最小的角度对应的点
A
3
{displaystyle A_{3}}
。若由
A
2
{displaystyle A_{2}}
到
A
3
{displaystyle A_{3}}
的路径相对
A
1
{displaystyle A_{1}}
到
A
2
{displaystyle A_{2}}
的路径是向右转的(可以想象一个人沿
A
1
{displaystyle A_{1}}
走到
A
2
{displaystyle A_{2}}
,他站在
A
2
{displaystyle A_{2}}
时,是向哪边改变方向),表示
A
3
{displaystyle A_{3}}
不可能是凸包上的一点,考虑下一点由
A
2
{displaystyle A_{2}}
到
A
4
{displaystyle A_{4}}
的路径;否则就考虑
A
3
{displaystyle A_{3}}
到
A
4
{displaystyle A_{4}}
的路径是否向右转……直到回到
A
1
{displaystyle A_{1}}
。这个算法的整体时间复杂度是
O
(
n
log
n
)
{displaystyle O(nlog {n})}
,注意每点只会被考虑一次,而不像Jarvis步进法中会考虑多次。这个算法由葛立恒在1972年发明。它的缺点是不能推广到二维以上的情况。将点按x坐标的值排列,再按y坐标的值排列。选择x坐标为最小值的点,在这些点中找出y坐标的值最大和y坐标的值最小的点。对于x坐标为最大值也是这样处理。将两组点中y坐标值较小的点连起。在这条线段下的点,找出它们之中y坐标值最大的点,又在它们之间找x坐标值再最小和最大的点……如此类推。时间复杂度是
O
(
n
log
n
)
{displaystyle O(nlog {n})}
。将点集X分成两个不相交子集。求得两者的凸包后,计算这两个凸包的凸包,该凸包就是X的凸包。时间复杂度是
O
(
n
log
n
)
{displaystyle O(nlog {n})}
。选择最左、最右、最上、最下的点,它们必组成一个凸四边形(或三角形)。这个四边形内的点必定不在凸包上。然后将其余的点按最接近的边分成四部分,再进行快包法(QuickHull)。
相关
- C00–D48ICD-10 第二章:肿瘤,为WHO规定的各类已发现的肿瘤。恶性肿瘤(C00-C97)淋巴、造血和有关组织的恶性肿瘤 (C81-C96)原位肿瘤 (D00-D09)良性肿瘤 (D10-D36)动态未定或动态未知的肿瘤(D37
- psi磅每平方英寸(pound per square inch或pound-force per square inch),缩写psi,英制压强单位,定义为1磅力在1平方英寸面积所产生的压强,符号 lbf/in2、lbf/in2。磅力每平方英寸常用
- 威塞克斯王国威塞克斯王国(古英语:Westseaxna rīce),意为“西撒克逊人的王国”,是盎格鲁-撒克逊人的王国。其立国时间是519年左右,开国者据说是率族人登陆英格兰汉普郡沿海地带的彻迪克。到了
- 细胞记忆细胞记忆,亦作身体记忆(Body memory)是一个伪科学假说,认为人体本身或身体上的所有细胞均有储存记忆或个性特质的能力,而不是主流学说所认为的只存在于大脑。这个假说可用来解释
- 东周前770年-前256年东周(前770年至前256年),是历史上对国都东迁以后的周朝的称呼,相对于之前国都在镐京的时期,即西周。东周也是“春秋时代”的开始。东周京都于前770年自镐京(今陕西
- 国语罗马字国语罗马字是一套官语汉字拉丁化方案,曾是中华民国国家标准。它和通字方案一样使用复杂的拼写规则来标示声调,不像其他方案要用到调号或数字。因为以拼写来标调,国语罗马字的拼
- 漂白漂白,一般指纺织领域染整工艺过程。漂白的目的是去除天然色素,赋于织物必要和稳定的白度。漂白的主要方法有氧化法和还原法。
- 和平主义和平主义又称非战主义(Pacifism),是反对战争或暴力的一切形式,追求和平和非暴力方式,解决人与人之间的冲突和对抗,信仰和支持和平主义的人称为和平主义者(Pacifist)。激进的和平主义
- 加拿大 U15 大学联盟U15是一个由15间加拿大顶尖研究型大学所组成的一个组织。第二次世界大战后,尤以麦基尔大学,多伦多大学为首的加拿大大学在学术界取得巨大的进步。1991年,经过多年积累后的加拿
- 雨层云雨层云(学名:Nimbostratus,缩写:Ns),属于低云族。其学名合成自拉丁语的nimbus(“雨云”)和stratus(“层状的,层云”)。雨层云覆盖全天,云体厚而呈暗灰色,常伴随持续性的降雨,也叫“雨云”