首页 >
凸包
✍ dations ◷ 2025-09-16 00:44:55 #凸包
在一个实数向量空间
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)。
相关
- 拉贾斯坦邦拉贾斯坦邦(印地语:राजस्थान,拉丁字母转写:Rajasthan)位于印度西部,与巴基斯坦相接壤,是印度境内的一个邦。该邦官方语言是拉贾斯坦语而除此之外包括信德语、古吉拉特语和
- 修业旅行壮游(英语:Grand Tour)是指自文艺复兴时期以后,欧洲贵族子弟进行的一种欧洲传统的旅行,后来也扩展到中欧、意大利、西班牙富有的平民阶层。壮游尤其盛行于18世纪的英国,留下了丰富
- 上升计划上升计划 (俄语:Восход,意思为“上升”或者“日出”)是一个苏联载人航天计划。上升计划是东方计划的后续,利用了东方计划被取消飞行留下的物资。上升计划的两次航天飞行
- 十字军国家十字军国家指经由十字军东征而建立之拉丁国家,他们建立国家时,一般都会将法兰克人那套成熟的采邑制度移植至新征服地,而他们所征服之地区,一般都会同时设立拉丁主教,这些国家之存
- 兰斯主教座堂兰斯主教座堂(Notre-Dame de Reims)是法国大东部大区城市兰斯的主教座堂,历史上曾经有25位法国君主在此加冕。教堂是大东部大区主要的名胜,2006年吸引了50万名游客。主教座堂大
- 邹族邹族(邹语:Cou),日治时期与战后初期称为曹族:104,为台湾南岛语族的一支。明治三十二年(1899年)伊能嘉矩在与粟野传之烝合撰的《台湾蕃人事情》中,将台湾原住民族分为七族与平埔族,并
- 索尼移动通信索尼移动通信股份有限公司(英语:Sony Mobile Communications Inc.,日语:ソニーモバイルコミュニケーションズ株式会社),简称索尼移动(Sony Mobile),是一家跨国性移动电话制造公司,在日
- 大汗可汗(拼音:Kèhán(叶音);古突厥语:
- 克莱尔学堂剑桥大学克莱尔学堂(英语:Clare Hall, Cambridge) 是剑桥大学的一个学院。克莱尔学堂是剑桥大学两所仅招收研究生的学院中的一所,另一所是达尔文学院。
- 朴叙俊朴叙俊(韩语:박서준,1988年12月16日-),原名朴容圭,韩国男演员。名字常被译作朴书俊、朴瑞俊。曾凭《金子轻松出来吧》获得第六届韩国电视剧节男子新人赏;以及凭《温暖的一句话》获得