凸包

✍ dations ◷ 2025-07-19 07:00:37 #凸包
在一个实数向量空间 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)。

相关

  • 步兵伙友步兵伙友(古希腊语:πεζέταιροι ; pezhētairoi),或译步行伙友。在字义上由希腊文中“步兵”(pezos)和“伙友”(hetairos)两词所组成。步兵伙友是马其顿军队中的重装步兵,原
  • 少尿症寡尿(英文:Oliguria),指排尿的量比正常人少。寡尿的定义因年龄差异而有所不同。寡尿通常是异常肾功能的最早征兆。
  • 世界末日世界末日包括以下几种层次:
  • Hsub2/sub[SiFsub6/sub]氟硅酸、六氟硅酸是化学式为H2SiF6的无机化合物,只存在于溶液中。纯H2SiF6不稳定,容易分解生成HF和SiF4。H2SiF6是氟磷灰石与氢氟酸反应的副产物,反应生成的HF与硅酸盐矿物反应
  • 鹿特丹大学鹿特丹伊拉斯姆斯大学(荷兰语:Erasmus Universiteit Rotterdam),也译作鹿特丹伊拉斯谟大学,位于荷兰南部城市鹿特丹,是享誉世界的著名公立大学。该校以荷兰中世纪著名的人文主义思
  • 种晶晶种是一小块单晶或多晶(通常是单晶),像种子般用来成长与自身相同材料、相同晶体结构的大晶体。无论把晶种浸入过饱和溶液,或使晶种与熔融材料接触并冷却,或者让材料蒸气在晶种表
  • 美洲原住民神话美洲原住民神话是美洲原住民的神话与故事,由于原住民神话身受萨满巫术文化影响,因此主要信仰与大自然的神灵相当接近,美洲原住民不仅敬畏神明,也敬畏大自然中的一草一木,相信即使
  • 病虫害防治病虫害防治(英语:Pest control)是指针对性地消灭一些害虫物种,来保障粮食产量、人类健康以及生态平衡的农业过程。从事病虫害防治这一行当的专家在美国被称为“扑灭者”(英语:Exte
  • 睡眠日记睡眠日记是一个人的睡眠时间和醒来时间的相关信息的记录,这个记录通常持续几个星期。它可以通过自己或他人来记录。记睡眠日记是国际公认的辅助检查睡眠疾病的方法,而每天记睡
  • 少女峰少女峰(德语:Jungfrau,4,158米),是同名的山脉断层中的最高峰。位于瑞士的境内,属阿尔卑斯山脉部分。断层中其余两峰为艾格峰(Eiger,3,970米)及僧侣峰(Mönch,4,107米)。少女峰于1811年才