凸包

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

相关

  • 定量构效关系定量构效关系(QSAR)是一种借助分子的理化性质参数或结构参数,以数学和统计学手段定量研究有机小分子与生物大分子相互作用、有机小分子在生物体内吸收、分布、代谢、排泄等生理
  • 教育学教育学是研究教育现象和教育问题,揭示教育规律的一门学科,是一门研究如何培养人的科学。教育学作为一种思想和想象,零星记载于当时的思想家、哲学家的言论和著作中,如柏拉图的《
  • 罗百氏傍人罗百氏傍人(Paranthropus robustus),又名粗壮傍人,是于1938年在南部非洲发现的化石。罗伯氏傍人的头颅骨发展倾向成为重型的咀嚼工具。由于它明显与南方古猿有关,故罗伯特·布鲁
  • 英格丽德·贝当古英格丽德·贝当古·普莱西奥(西班牙语:Íngrid Betancourt Pulecio,1961年12月25日-),哥伦比亚法国裔的政治家,曾任哥伦比亚参议员及反贪污活跃人士。贝当古于2002年2月23日被反政
  • Mg(NOsub3/sub)sub2/sub硝酸镁是镁元素的硝酸盐,具有吸湿性,在潮湿的空气中能快速与水反应形成六水合硝酸镁。硝酸镁易溶于水或乙醇。水溶液呈弱酸性。硝酸镁的主要用途是浓缩硝酸,并常被用于印刷业及
  • 芦苇芦苇(学名:Phragmites communis),又称普通芦苇(common reed),是生长于沼泽、河沿、海滩等湿地的一种禾本科植物,遍布于全世界温带和热带地区,芦苇属的植物大约有10种,有的分类学家认为
  • 环肽环肽(cyclic peptide)是包含环状键序列的多肽链。 这可以通过肽的氨基和羧基末端之间的连接来实现,例如在环孢素中。 氨基端和侧链之间的连接,例如杆菌肽中的连接; 羧基末端和侧
  • 富士山富士山(日语: 富士山/ふじさん Fujisan ?)是日本一座横跨静冈县和山梨县的活火山,位于东京西南方约80公里处,主峰海拔3776米,2002年8月(平成14年),经日本国土地理院重新测量后,为377
  • 环球购物中心环球购物中心(英语:Global Mall)是台湾建筑商冠德建设所转投资创立的一家连锁购物中心,环球购物中心的店型分为全客型中大型购物中心与车站型中小型购物中心两类,目前在台湾台北
  • 石之玫石之玫,甘泉人,清朝政治人物。同进士出身。顺治十五年(1658年)戊戌科进士。康熙三十一年接替王原直任福州府知府一职,康熙三十三年由王纪接任。