首页 >
凸包
✍ dations ◷ 2025-09-08 07:52:19 #凸包
在一个实数向量空间
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)。
相关
- 特征中文里的特征可能有以下意义:在生物学中:在数学中:
- 奥古斯塔MV AGUSTA(中文名“奥古斯塔”)是一家意大利的摩托车制造商。Count Domenico Agusta在1945年以小排气量的二行程车起家,创立了 Moto Verg-hera Agusta(简称 MV AGUSTA)·他热爱赛
- DNA重组重组DNA是一种人工合成的脱氧核糖核酸。它是把一般不同时出现的DNA序列组合到一起而产生的。从遗传工程的观点来看重组DNA是把相关的DNA添加到已有生物的基因组中,比如细菌的
- 自由民主人民党自由民主人民党(荷兰语:Volkspartij voor Vrijheid en Democratie,缩写为VVD)是荷兰的一个保守自由主义政党。自民党是以自由主义思想为基础,传统上是最支持自由市场的荷兰政党,致
- 彼得·希格斯彼得·威尔·希格斯,CH,FRS,FRSE(英语:Peter Ware Higgs,1929年5月29日-),英国理论物理学家,爱丁堡大学荣誉退休教授,他以希格斯机制与希格斯粒子而闻名于世。彼得·希格斯出生在英格兰
- span style=color:#0055AA;大气/span地球大气层,又称大气圈,因重力关系而围绕着地球的一层混合气体,是地球最外部的气体圈层,包围着海洋和陆地,大气圈没有确切的上界,在离地表2000-16000公里高空仍有稀薄的气体和基本
- 乾闼婆乾闼婆 gān tà pó(梵语:गन्धर्व,转写:Gandharva,巴利语:Gandhabba),在印度宗教中,是一种以香味为食的男性神,能表演音乐、节目;又音译为.mw-parser-output ruby.zy{text-alig
- 许筠许筠(허균,1569年-1618年),字端甫,号蛟山、惺所、惺叟、又号白月居士,朝鲜王朝中期的文臣和政治人、诗人、作家、小说家。本贯阳川许氏。他是小说《洪吉童传》的著者。许筠于1569年
- 艾伯特湖阿尔伯特湖(Lake Albert;Lac Albert)是位于非洲中部乌干达和刚果民主共和国边界的淡水湖,它是大湖地区的非洲大湖之一。它是非洲的第七大湖,和世界的第二十七大湖。阿尔伯特湖位
- 引力透镜引力透镜效应(gravitational lensing),根据广义相对论,就是当背景光源发出的光在引力场(比如星系、星系团及黑洞)附近经过时,光线会像通过透镜一样发生弯曲。光线弯曲的程度主要取