首页 >
凸包
✍ dations ◷ 2024-07-03 06:33: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)。
相关
- 子宫卵巢摘除术子宫卵巢摘除术是指通过医学手段,摘除哺乳动物的卵巢。此手术方式为不可逆手术,一旦进行了便不可能再次回复怀孕的可能性。一般来说如非是肿瘤等问题,一般人类不太会选择此方式
- 观念概念是抽象的、普遍的想法,是充当指明实体、事件或关系的范畴或类的实体。在它们的外延中忽略事物的差异,如同它们是同一的去处理它们,所以概念是抽象的。它们等同的适用于在它
- 氯气弹含有氯气的炮弹,为化学武器,有毒性,在施放之后会释放大量氯气以毒杀敌人。由德国科学家弗里茨·哈伯(Fritz Haber)所研发,第一次世界大战期间,在1915年由德国陆军首次在军事用途上
- 亲潮亲潮((日语:親潮/おやしお oyashio,英语:Oyashio current)),或又称为千岛群岛洋流(日语:千島海流/ちしまかいりゅう chishima kairyū,英语:Kuril Current),是一股北太平洋亚寒带(英语:Subar
- 馥芮白馥芮白(Flat White)是一种流行于澳大利亚及新西兰的,以意式浓缩为基底的咖啡。馥芮白与拿铁、卡布奇诺有些相似。区别在于馥芮白使用更少的奶泡,从而获得较大的咖啡比例,品尝时更
- 行政法规行政法规指政府行政部门制定的法规、规章、规则,有别于立法机构颁布的法案或法院判决构成的判例以及司法解释。在中华人民共和国,行政法规指中华人民共和国国务院根据全国人民
- 赫雷罗人和纳马人大屠杀赫雷罗人和纳马人大屠杀是1904年至1908年德意志帝国在德属西南非洲针对赫雷罗人、纳马人(英语:Nama people)、萨恩人实行了连坐屠杀,被认为是二十世纪的第一场种族屠杀。出于对
- 先令“先令”(Shilling)曾经是英国,前英国附庸国或附属国与英联邦(Commonwealth)国家的货币单位。“先令”这个字源于盎格鲁撒克逊时期的古英语Scilling,是当时的会计名词,大约相等于当
- 东约克郡约克郡东区(英语:East Riding of Yorkshire),通称东约克郡,直译约克郡东瑞丁,英国英格兰约克郡-亨伯地区的名誉郡、非都市区(Non-metropolitan district)、单一管理区。行政总部位于
- 前聘叶赫之女北关老女(1583年-1616年),叶赫那拉氏,本名不详,海西女真叶赫部西城贝勒布寨女,末代贝勒布扬古妹。努尔哈赤福晋孟古哲哲的堂侄女,年龄只比她小八岁。兄长布扬古曾将她许嫁努尔哈赤,但