Convex_Hull
- 格式：ppt
- 大小：79.00 KB
- 文档页数：12
下载文档原格式
合集下载
第3讲 凸集、凸函数、凸规划 Convex Set、Convex Function、Convex Programming
定义 锥、凸锥
设S R , x0 S，如果对一切 xS
n
及 0, 有x 0 x S, 则称S是 以x 0为顶点的锥. 如果S又是凸集， 则称S为凸锥.
凸函数
凸函数(Convex Function) ----定义2.4 设 D R n 是非空凸集， f x : S R, 若对任意的 x , y D , 及任意的 0, 1
f x 1 y f x 1 f y 都有：
则称函数 f x 为 D 上的凸函数．
注：将上述定义中的不等式反向，可以得到 凹函数的定义．
凸函数
严格凸函数 设 D R n 是非空凸集， f x : S R, 若对任意的 x, y D ( x y), 及任意的 0,1 则称函数 f x 为 D
上的严格凸函数．
都有：f x 1 y f x 1 f y
注：将上述定义中的不等式反向，可以 得到严格凹函数的定义．
凸函数
几何性质
0 1 表示连接 x1 , f x1 , x2 , f x2 的线段． f x1 1 x2 表示在点 x1 1 x2处的
例：D1 x,0T x R 表示 x 轴上的点．
D2
T
0, y
y R表示 y 轴上的点．
则 D1 D2 表示两个轴的所有点， 它不是凸集； 而 D1 D2 R 2 凸集．
凸集-----凸包(Convex Hull)
定义 设 S R , S 中任意有限个点的所有凸 组合所构成的集合称为S的凸包，记为H(S),即
第 3讲
凸集、凸函数、凸规划
设S R , x0 S，如果对一切 xS
n
及 0, 有x 0 x S, 则称S是 以x 0为顶点的锥. 如果S又是凸集， 则称S为凸锥.
凸函数
凸函数(Convex Function) ----定义2.4 设 D R n 是非空凸集， f x : S R, 若对任意的 x , y D , 及任意的 0, 1
f x 1 y f x 1 f y 都有：
则称函数 f x 为 D 上的凸函数．
注：将上述定义中的不等式反向，可以得到 凹函数的定义．
凸函数
严格凸函数 设 D R n 是非空凸集， f x : S R, 若对任意的 x, y D ( x y), 及任意的 0,1 则称函数 f x 为 D
上的严格凸函数．
都有：f x 1 y f x 1 f y
注：将上述定义中的不等式反向，可以 得到严格凹函数的定义．
凸函数
几何性质
0 1 表示连接 x1 , f x1 , x2 , f x2 的线段． f x1 1 x2 表示在点 x1 1 x2处的
例：D1 x,0T x R 表示 x 轴上的点．
D2
T
0, y
y R表示 y 轴上的点．
则 D1 D2 表示两个轴的所有点， 它不是凸集； 而 D1 D2 R 2 凸集．
凸集-----凸包(Convex Hull)
定义 设 S R , S 中任意有限个点的所有凸 组合所构成的集合称为S的凸包，记为H(S),即
第 3讲
凸集、凸函数、凸规划
Matlab中图像函数大全 2
Matlab中图像函数大全2matlab 2009-10-26 21:08:13 阅读900 评论0 字号：大中小订阅边学边和大家交流，我将我在学习中搜集到的资料和大家分享！图像处理函数详解——strel功能：用于膨胀腐蚀及开闭运算等操作的结构元素对象(本论坛随即对膨胀腐蚀等操作进行讲解)。
用法：SE = strel(shape,parameters)创建由指定形状shape对应的结构元素。
其中shape的种类有arbitrary''pair''diamond''periodicline''disk''rectangle''line''square''octagon参数parameters一般控制SE的大小。
例子：se1 = strel('square',6)% 创建6*6的正方形se2 = strel('line',10,45)% 创建直线长度10，角度45se3 = strel('disk',15)% 创建圆盘半径15se4 = strel('ball',15,5)% 创建椭圆体，半径15，高度5图像处理函数详解——roipoly功能：用于选择图像中的多边形区域。
用法：BW = roipoly(I,c,r)BW = roipoly(I)BW = roipoly(x,y,I,xi,yi)[BW,xi,yi] = roipoly(...)[x,y,BW,xi,yi] = roipoly(...)BW = roipoly(I,c,r)表示用向量c、r指定多边形各点的X、Y坐标。
BW选中的区域为1，其他部分的值为0.BW = roipoly(I)表示建立交互式的处理界面。
BW = roipoly(x,y,I,xi,yi)表示向量x和y建立非默认的坐标系，然后在指定的坐标系下选择由向量xi，yi指定的多边形区域。
Regionprops浅析
短轴与长轴相反，使区域绕直线旋转的转动惯量最大
MajorAxisLength：与区域具有相同标准二阶中心矩的椭圆的长轴长度 用途：近似判断区域长度
MinorAxisLength：与区域具有相同标准二阶中心矩的椭圆的短轴长度 用途：近似判断区域宽度
欧拉数应用：
孔洞计数
不规则物体计数
BoundingBox：找到包含该连通区域的最小矩形 实现：根据pixellist，找横纵坐标的最小值和最大值即可得左上角和右下角的坐标 输出：左上角的坐标和矩阵的高宽。[x（列号），y（行号），矩形高度，矩形宽度]
Extent：返回连通区域和其最小边界矩形中的像素比例 （ Area/边界框区域） 用途：判断区域矩形度。值越趋近于1，区域越趋近于矩形
1} =[51:150] 2} =[38:174] 1} =[184,325] 2} =[225.334]
EquivDiameter：与区域具有相同面积的圆的直径 EquivDiameter = sqrt(4*Area/pi) 用途：判断区域圆度
S1
A
B
S2
（1~2）划分两个子集中的点
奇数码： 偶数码： （角点）
旋转30度
扩展：判断区域是否是个圆？
perimeterOld = 44.8 perimeter = 43.1
perimeterOld = 47.7 perimeter = 44.5
metric = 4*pi*area/perimeter^2；metric值越趋近于1则越圆
ConvexArea：返回填充区域凸多边形图像中的像素个数
Solidity：统计在区域和其最小凸多边形中的像素比例 Solidity = Area/ConvexArea 用途：计算凸性
Regionprops浅析
作用 填充区域图像中的像素个数 与某区域具有相同大小的填充逻辑矩阵 与某区域具有相同大小的逻辑矩阵 与区域具有相同标准二阶中心矩的椭圆的长轴长度 与区域具有相同标准二阶中心矩的椭圆的短轴长度 与区域具有相同标准二阶中心矩的椭圆的长轴与x轴的交角 图像各个区域边界地区的周长 存储区域像素的索引下标
PixelList Solidity
测量类型properties作用area图像各个区域中像素总个数boundingbox包含相应区域的最小矩形centroid每个区域的质心重心convexarea填充区域凸多边形图像中的on像素个数convexhull包含某区域的最小凸多边形的边界像素坐标conveximage返回包含区域最小凸多边形的逻辑矩阵eccentricity与区域具有相同标准二阶中心矩的椭圆的离心率equivdiameter与区域具有相同面积的圆的直径eulernumber欧拉数区域中的对象数减去这些对象中的孔数extent同时在区域和其最小边界矩形中的像素比例extrema八方向区域极值点properties作用filledarea填充区域图像中的像素个数filledimage与某区域具有相同大小的填充逻辑矩阵image与某区域具有相同大小的逻辑矩阵majoraxislength与区域具有相同标准二阶中心矩的椭圆的长轴长度minoraxislength与区域具有相同标准二阶中心矩的椭圆的短轴长度orientation与区域具有相同标准二阶中心矩的椭圆的长轴与x轴的交角perimeter图像各个区域边界地区的周长pixelidxlist存储区域像素的索引下标pixellist存储上述索引对应的像素坐标solidity同时在区域和其最小凸多边形中的像素比例subarrayidx每个连通区域边界框中的元素索引?pixelidxlist
Matlab图像处理函数：regionprops
Matlab图像处理函数：regionprops这⾥给出在Matlab图像处理⼯具箱中⾮常重要的⼀个图像分析函数：regionprops。
顾名思义：它的⽤途是get the properties of region，即⽤来度量图像区域属性的函数。
语法STATS = regionprops(L,properties)描述测量标注矩阵L中每⼀个标注区域的⼀系列属性。
L中不同的正整数元素对应不同的区域，例如：L中等于整数1的元素对应区域1；L中等于整数2的元素对应区域2；以此类推。
返回值STATS是⼀个长度为max(L(:))的结构数组，结构数组的相应域定义了每⼀个区域相应属性下的度量。
properties 可以是由逗号分割的字符串列表、饱含字符串的单元数组、单个字符串 'all' 或者 'basic'。
如果 properties 等于字符串 'all'，则所有下述字串列表中的度量数据都将被计算，如果 properties 没有指定或者等于 'basic'，则属性: 'Area', 'Centroid', 和 'BoundingBox' 将被计算。
下⾯的列表就是所有有效的属性字符串，它们⼤⼩写敏感并且可以缩写。
属性字符串列表Area EquivDiameter MajorAxisLengthBoundingBox EulerNumber MinorAxisLengthCentroid Extent OrientationConvexArea Extrema PixelIdxListConvexHull FilledArea PixelListConvexImage FilledImage SolidityEccentricity Image属性详细定义本部分将结合⼀个具体的例⼦说明各种字串相关属性的意义，矩阵取⾃在蚁蛉模式识别中做过预处理后的斑纹分割图像，如下图：这是⼀幅⼆值图像，在应⽤regionprops函数之前必须将其标注，可以调⽤ bwlabel函数和伪彩⾊处理，标注后的图像如下图：下⾯基于以上的材料来考察属性的含义。
逐次凸逼近算法代码
逐次凸逼近算法代码逐次凸逼近算法（Sequential Convex Programming, 简称SCP）是一种求解非线性规划问题的有效算法。
SCP算法通过不断剖分一组凸包来逐渐逼近非凸问题的最优解。
以下是SCP算法的Python实现。
输入参数:- `f`: 目标函数- `G`: 约束条件- `x0`: 初始点- `tol`: 目标函数值的最大误差```import numpy as npfrom scipy.optimize import minimize_scalardef scp(f, G, x0, tol):n = len(x0) # 变量数量x = x0 # 初始点while True:# 计算凸包 vertices 和 coefvertices, coef = calc_convex_hull(f, G, x)# 计算在vertices上的最小函数值v_min = np.inffor vertex in vertices:v = f(vertex)if v < v_min:v_min = vx_min = vertex# 如果目标函数值满足要求，返回解if v_min < tol:return x_min# 寻找在凸包上最小的、与本次搜索方向相反的梯度grad_max = -np.inffor i in range(len(vertices)):grad = G(vertices[i]).dot(coef[i])if grad > grad_max:grad_max = gradx_max = vertices[i]# 用线性搜索找到下一个xdef df(alpha):return np.linalg.norm(G(x+alpha*(x_max-x)))res = minimize_scalar(df, bounds=(0,1), method='bounded')alpha = res.xx = x + alpha*(x_max-x)def calc_convex_hull(f, G, x):# 计算梯度和海森矩阵grad = G(x)hess = np.zeros((len(x),len(x)))for i in range(len(x)):hess[i,i] = np.sum(G.jacobian(x, i)**2)for j in range(i+1,len(x)):hess[i,j] = hess[j,i] = G.jacobian(x, i).dot(G.jacobian(x, j))# 计算梯度投影的y轴长度y = gradp = np.zeros_like(grad)for i in range(len(x)):d = grad[i]for j in range(i):d -= p[j]*hess[i,j]p[i] = d/hess[i,i]y -= p[i]*grad[i]y = np.sqrt((y**2).sum())# 计算凸包y_max = -np.infvertices_max = []for i in range(2**len(x)):x_i = np.array([int(a) for a in np.binary_repr(i, width=len(x))])if np.abs(x_i).sum()==1:if np.sign(x_i.dot(grad))==1:x_root = x - x_i*grad/hess.diagonal()x_vertex = scp(lambda v: -f(v), lambda v: -G.jacobian(v), x_root, tol=1e-6)y_vertex =-G(x_vertex).dot(grad)/np.sqrt(G(x_vertex).dot(hess).dot(G(x_vertex)))if y_vertex > y_max:y_max = y_vertexvertices_max = []if np.isclose(y_vertex, y_max):vertices_max.append(x_vertex)# 计算凸包边界coef = []vertices = vertices_max.copy()for i in range(len(vertices_max)):j = (i+1)%len(vertices_max)v =(vertices_max[j]-vertices_max[i])/np.linalg.norm(vertices_max[j]-vertices_max[ i])coef.append(-v.dot(grad))while True:# 找到第一个顶点k = Nonefor i in range(len(vertices)):n_i = (i-1)%len(vertices)v_i = vertices[i] - vertices[n_i]s_i = np.sign(coef[i]-coef[n_i])if np.linalg.norm(G(vertices[i])-G(vertices[n_i]))>1e-10:w_i =s_i*v_i.dot(G(vertices[i])-G(vertices[n_i]))/np.linalg.norm(G(vertices[i])-G(v ertices[n_i]))if w_i > 1e-8:k = ibreakif k is None:break# 找到下一个顶点k_next = Nonefor i in range(len(vertices)):if i==k: continuev_i = vertices[i] - vertices[k]s_i = np.sign(coef[i]-coef[k])if np.linalg.norm(G(vertices[i])-G(vertices[k]))>1e-10:w_i =s_i*v_i.dot(G(vertices[i])-G(vertices[k]))/np.linalg.norm(G(vertices[i])-G(ver tices[k]))if w_i > 1e-8:if k_next is None:k_next = icontinuev_k = vertices[k_next] - vertices[k]s_k = np.sign(coef[k_next]-coef[k])ifnp.linalg.norm(G(vertices[k_next])-G(vertices[k]))>1e-10:w_k =s_k*v_k.dot(G(vertices[k_next])-G(vertices[k]))/np.linalg.norm(G(vertices[k_ne xt])-G(vertices[k]))if w_k > w_i:k_next = iif k_next is None:breakvertices.insert(k_next if k_next<k else k+1,vertices[k]+v_i*w_i/(w_i-w_k))coef.insert(k_next if k_next<k else k+1,coef[k]+(coef[i]-coef[k])*w_i/(w_i-w_k))return vertices, coef```这个代码做了以下几件事情：1. `calc_convex_hull`: 对于当前解 `x`，计算出它所在点的基于梯度和海森矩阵的凸包 `vertices` 和对应的法向量`coef`。
hive空间函数
Hive是基于Hadoop的数据仓库工具，支持SQL语句和类SQL语句，提供了一些空间函数，用于处理空间数据。
以下是常用的Hive空间函数：
1. ST_Area：计算几何图形的面积。
2. ST_Boundary：返回几何图形的边界。
3. ST_Centroid：计算几何图形的重心。
4. ST_ConvexHull：计算几何图形的凸壳。
5. ST_Contains：判断一个几何图形是否包含另一个几何图形。
6. ST_Crosses：判断两个几何图形是否交叉。
7. ST_Disjoint：判断两个几何图形是否不相交。
8. ST_Envelope：返回几何图形的最小外接矩形。
9. ST_Equals：判断两个几何图形是否相等。
10. ST_Intersects：判断两个几何图形是否交叉。
11. ST_PointOnSurface：返回几何图形表面上的一个点。
12. ST_SymDifference：返回两个几何图形的对称差集。
13. ST_Union：返回多个几何图形的并集。
14. ST_Within：判断一个几何图形是否在另一个几何图形内部。
15. ST_X：返回几何图形的x坐标。
16. ST_Y：返回几何图形的y坐标。
这些空间函数在处理空间数据时非常有用，例如可以用于计算地理区域的面积、周长、重心等信息，判断两个地理位置之间的距离、相交关系等。
opencv最大内切圆 算法原理
OpenCV最大内切圆算法原理详解1. 引言最大内切圆是指在给定的轮廓中，能够与轮廓相切且具有最大半径的圆。
在计算机视觉和图像处理中，最大内切圆算法经常被用于形状分析、目标检测和轮廓匹配等应用。
OpenCV作为一个开源的计算机视觉库，提供了一系列用于图像处理和分析的函数和算法，其中也包括了计算最大内切圆的函数。
本文将详细介绍与OpenCV最大内切圆算法原理相关的基本原理，包括最大内切圆的定义、计算方法和实现步骤等内容。
2. 最大内切圆的定义最大内切圆是指在给定的轮廓中，能够与轮廓相切且具有最大半径的圆。
具体而言，对于一个给定的轮廓，最大内切圆的圆心位于轮廓内部，并且与轮廓的边界相切，同时其半径是所有与轮廓相切的圆中最大的。
3. 最大内切圆的计算方法计算最大内切圆的方法可以分为两步：首先，找到轮廓的凸包；然后，计算凸包的最大内切圆。
3.1 凸包的计算凸包是指包围给定点集合的最小凸多边形。
在计算最大内切圆之前，需要先计算轮廓的凸包。
OpenCV提供了函数cv2.convexHull()来计算凸包。
凸包的计算步骤如下： 1. 读入轮廓数据。
2. 使用cv2.convexHull()计算凸包。
3. 绘制凸包。
3.2 最大内切圆的计算在得到轮廓的凸包之后，可以计算凸包的最大内切圆。
最大内切圆的计算可以通过迭代法来实现。
最大内切圆的计算步骤如下： 1. 初始化最大内切圆的半径为0。
2. 对于凸包上的每个点，计算以该点为圆心的最大内切圆。
3. 如果计算得到的最大内切圆的半径大于当前的最大半径，则更新最大内切圆的半径和圆心。
4. 绘制最大内切圆。
4. OpenCV中计算最大内切圆的实现步骤在OpenCV中，可以使用以下步骤来计算最大内切圆： 1. 读入图像并进行预处理，如灰度化、二值化等。
2. 使用OpenCV函数cv2.findContours()找到图像中的轮廓。
3. 对于每个轮廓，使用cv2.convexHull()计算凸包。
Matlab中图片保存的四种方法
Matlab中图片保存的四种方法一种是出来图形窗口后手动保存（这儿又可以分两种）：1 直接从菜单保存，有fig,eps,jpeg,gif,png,bmp等格式。
2 edit------〉copy figure，再粘贴到其他程序。
另一种是用命令直接保存（这里也有两种）：1 用saveas命令保存图片。
saveas的三个参数：（1）图形句柄，如果图形窗口标题栏是“Figure 3”,则句柄就是3.（2）文件名。
（3）单引号字符串，指定存储格式。
例：saveas(gcf,['D:\MATLAB7\work','yanbao',num2str(k),'.jpg']);2 使用plot函数后紧接着用print函数。
print的三个参数：（1）图形句柄，如果图形窗口标题栏是“Figure 3”,则句柄就是3.（2）单引号字符串，指定存储格式。
用gcf可以获取当前窗口句柄。
png格式：'-dpng'jpeg: '-djpeg',tiff: '-dtiff'bmp: '-dbitmap'（3）文件名。
例：>> x=-pi:2*pi/300:pi;>> y=sin(x);>> plot(x,y);>> print(gcf,'-dpng','abc.png') % 保存为png格式的图片。
>> figure(2) % 新建一个句柄为2的图形窗口。
>> plot(x,cos(x)); % 在句柄为2的图形窗口上画图。
>> grid>> print(2,'-djpeg','C:\abc.jpeg'); %将句柄为2的图形保存为jpeg/jpg格式的图片，文件名为'C:\abc.jpeg'。
凸优化理论笔记
x (a1 , a2 ) 1 b x2
√
×
×
10. 欧几里得空间中的球：
B ( xc , r ) x || x xc ||2 r , xc R n , r R
11. 欧几里得空间中的椭球：
√
E ( xc , r , P ) x ( x xc )T P 1 ( x xc ) r , xc R n , r R, P 正定
一条直线是凸集，一条线段也是凸集
平面是凸集，一块矩形区域也是凸集
凸组合（Convex Combination） 设 k 个点 x1 , x2 , , xk ，
1 , 2 , , k [0,1] 1 2 k 1
则称 1 x1 2 x2 k xk 为 x1 , x2 , , xk 的凸组合 凸包（Convex Hull） 任意集合 C R ， C 中任意元素的凸组合构成的集合称凸包
非凸集的凸包
凸锥（Convex Cone） 定义： C 是仿射集↔ x1 , x2 C ，对 1 , 2 0 ，有 1 x1 2 x2 C
过原点的射线是凸锥
过原点的两条射线之间的区域是凸锥
பைடு நூலகம்
凸锥组合（Convex Cone Combination） 设 k 个点 x1 , x2 , , xk ， 1 , 2 , , k 0 则称 1 x1 2 x2 k xk 为 x1 , x2 , , xk 的凸锥组合 凸锥包（Convex Cone Hull） 任意集合 C R ， C 中任意元素的凸锥组合构成的集合称凸锥包
向量中r个最大元素之和sumlargestcomponents先求值再做线性变换变换的是值域先做线性变换再求值变换的是定义域无限个凸函数的极大值函数pointwisesupremumoverinfinitesetconvexfunctions均为x的凸函数则为凸函数
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
convex
not convex
Convex hulls
Preliminaries and definitions Vertices A polygon vertex is convex if its interior angle It is reflex if its interior angle > reflex convex
In a convex polygon, all the vertices are convex. In other words, any polygon with a reflex vertex is not convex.
Convex hulls
Preliminaries and definitions Convex hull, definition 2 The convex hull H(S) of a subset of points S in a plane is the set of all convex combinations of the points of S. It should be intuitively clear that a hull defined in this way can not have a “dent” (reflex vertex). Note now that S in this definition is an infinite set. The convex hull is the smallest convex set that contains S. To be more precise, it is the intersection of all convex sets that contain S.
Imagine nails pounded halfway into the plane at the points of S. The convex hull corresponds to a rubber band stretch around them.
Convex hulls
Preliminaries and definitions Convex polygon A polygon is convex iff for any two points in the polygon (interior boundary) the segment connecting the points is entirely within the polygon.
Convex hulls
Preliminaries and definitions Convex hull, definition 6 The convex hull H(S) of a set of points S in d dimensions is the set of all convex combinations of d + 1 or fewer points of S. This is different from definition 1 in that only d + 1 or fewer points are needed to get any point of H(S). S is again a finite set as in definition 1. For example, in the plane d = 2, convex polygons can be composed as the union of all points contained by the triangles of the given points, which are the convex combination of all d + 1 = 3 points.
Many triangles are not shown in the figure.
Convex hulls
Preliminaries and definitions Convex hull, definition 8 The convex hull H(S) of a set of points S in the plane is the enclosing convex polygon P with the smallest area. Convex hull, definition 9 The convex hull H(S) of a set of points S in the plane is the enclosing convex polygon P with the smallest perimeter. Extreme Points E A point p of a convex set is an extreme point if no two points a,b S exist such that p is between the line segment ab. Thus in Definition 6 example, the points (1,2 ,3,4,5,6,7) are extreme points but 8 and 9 and others are not. Alternately, the extreme points of S is the smallest subset of S having the property that H(E)=H(S). Thus E defines the vertices on H(S) but does not define the convex hull H(S) which requires the sequence of points on the hull viz. (1,3,4,2,6,7,5) for our example. Thus, there are two distinct problems.
Convex hulls
Preliminaries and definitions Convex hull, definition 3 The convex hull H(S) is the intersection of all convex sets that contain S. This is an intersection of an infinite number of Convex sets.
Convex hulls
Preliminaries and definitions Convex hull, definition 4 The convex hull H(S) of a set of points S in the plane is the smallest convex polygon P that encloses S, smallest in the sense that there is no other polygon P such that P P S.
Convex hulls
Preliminaries and definitions Problem definitions CONVEX HULL INSTANCE. A set S = {p1, p2, …, pN} of d-dimensional points. QUESTION. Construct the convex hull H(S) for S. (The construction must give the vertices and their sequence, that is, obtain a description of the boundary which is a convex ploygon.) EXTREME POINTS INSTANCE. A set S = {p1, p2, …, pN} of d-dimensional points. QUESTION. Identify the points of S that are vertices of the convex hull H(S). (Here the ordering is not required.) We will assume d = 2 unless otherwise noted. It turns out that both have the same asymptotic complexity (nlogn) for d=2. Thus the second problem is not any easier than the first problem.
Convex Hull
- most ubiquitous structure in computational geometry -useful to construct other structures -many applications: robot motion planning, shape analysis etc. - a beautiful object, one of the early success stories in computational geometry that sparked interest among Computer Scientists by the invention of O(nlogn) algorithm rather than a O(n**3) algorithm. - intimately related to sorting algorithm for both lower and upper bound.
P
P
Convex hulls
Preliminaries and definitions Convex hull, definition 5 The convex hull H(S) is the intersection of all halfspaces (for d = 2, halfplanes) that contain S. Actually, the number of such half planes is infinite but it can be defined as the intersection of a finite number of half planes. The hull construction algorithm essentially identifies these half planes.