首页 >
凸包
✍ dations ◷ 2025-10-06 22:27:08 #凸包
在一个实数向量空间
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)。
相关
- 多多纳多多纳(多立克希腊语Δωδώνα, 爱奥尼亚希腊语:Δωδώνη, Dòdònè)是位于希腊西北部伊庇鲁斯的一个神谕处。虽然多多纳最早的铭文历史只能追溯至约公元前550-560年,但
- 高加索犹太人高加索犹太人,分布于高加索山,尤其是阿塞拜疆与达吉斯坦、车臣。北高加索一向有犹太人居住,但他们并不包括格鲁吉亚犹太人。他们被称为是多才多艺的骑马战士。历史记载人口约为
- 楚科奇-堪察加语系楚科奇-堪察加语系,又名罗拉维特兰语系(Luorawetlan),是古西伯利亚语言的其中一种,通行于东北西伯利亚。虽然古西伯利亚语言本身的成员未必有关连,但楚科奇-堪察加语族之内的语言
- 被子植物传统分类方式:Anthophyta Magnoliophyta Cronquist, Takht. & W.Zimm., 1966被子植物(学名:Angiosperms),又名开花植物或有花植物。(以前的生物学分类称“被子植物门”,而现今被归
- 利伯蒂县自由县(Liberty County, Georgia)是位于美国乔治亚州东部的一个县,东傍大西洋。面积1,561平方公里。根据美国人口调查局2000年统计,共有人口61,610人。县治罕斯维(Hinesville)。成
- 全印电视台全印电视台(印地语:दूरदर्शन,拉丁字母转译为:DoorDarshan,简写为DD),是印度的国家电视台,也是印度最大的电视台。隶属于印度政府新闻广播部下属的印度广播公司。全印电视台
- Seymour Martin Lipset西摩·马丁·利普塞特(Seymour Martin Lipset,1922年3月18日-2006年12月31日),美国著名比较社会学家。代表作《政治人:政治的社会基础》(Political Man:The Social Bases of Politic
- 门齿门齿(Incisor)是异齿型哺乳类动物的第一类牙齿。不少草食性和杂食性的哺乳类,诸如人类和马匹,均需以门齿来切断食物。而肉食性动物,诸如猫科和犬科动物,它们的门齿较少,会以犬齿和
- 妓生妓生是朝鲜半岛的传统艺妓,在古代为朝鲜国王、两班等提供歌舞表演。妓生作为一个社会阶层最早出现在高丽王朝时期,其社会地位在高丽王朝和朝鲜王朝时期属贱民。妓生都接受过相
- 日本隐杆线虫秀丽隐杆线虫(学名:Caenorhabditis elegans)是一种非寄生性线虫,身体透明,长度约1毫米,主要分布在温带地区的土壤中。其寿命约两至三周,其中发育时间在三天左右,分为胚胎期、幼虫期