有限平面点集强可见点对的O(n~2logn)算法

1引言计算机图形可见性问题是离散计算几何、计算机图形学、模式识别等研究与应用领域中的一个重要问题~[1-2],关于有限平面点集强可见点对的几何结构以及结构以及应用在文献[3]中有较     

“凸包”的应用

定义1 对于平面图形内的任意两点A、B,线段AB上的所有点都在形内,这样的平面图形叫做凸形。显然,平面几何中研究的线段,三角形、凸多边形等都是凸形。定义2 对于平面上的有限个点所组成的平面点集,存在一个凸多边形,它包含这整个点集,且其顶点与这集的点重合。这样的凸多边形称为已知点集的凸包。特殊地,当平面上的点在一直线上时,凸包为线段。平面上有限点集的凸包的存在性从直观上看是显然的。在给定的有限个点的每个点插上大头针,用一根线圈上这些针,拉紧后构成的图形就是凸包。自然,这个直观的考虑不是凸包存在性的严格证明,     

N维点集凸包的计算机生成原理与方法

本文提出计算N维点集凸包问题的一个新算法,其基本作法是:首先生成一基本凸包,然后逐次依该基本凸包的诸面及法向为基础生成新的顶点集并形成更大的部分凸包,如此逐步递归地系统生成所求凸包的全部顶点及面.与已知的Chand-kapur方法相比,该算法每增加一个新的顶点不需求解线性代数方程组,从而计算效率大大提高.     

基于CCH的SVM几何算法及其应用

支持向量机(support vector machine(SVM))是一种数据挖掘中新型机器学习方法.提出了基于压缩凸包(compressed convex hull(CCH))的SVM分类问题的几何算法.对比简约凸包(reducedconvex hull(RCH)),CCH保持了数据的几何体形状,并且易于得到确定其极点的充要条件.作为CCH的实际应用,讨论了该几何算法的稀疏化方法及概率加速算法.数值试验结果表明所讨论的算法可降低核计算并取得较好的性能.     

R~n中构形和单纯复形的一个最优度量不等式

对于R~n中一般位置的点构形,定义了第r个极小凸包距离的概念,证明了极小凸包距离和极小点-超平面距离之间的一个最优不等式.该不等式的一个直接推论是:对于R~n中一个k-维单纯复形K,我们能用其顶点集的极小点-超平面距离下估计K的Gromov-Guth厚度.进一步,在每一个维数k,构造了例子说明该下界几乎是最优的.     

两个凸紧集的差及Clarke广义Jacobi与拟微分的关系

将犚狀空间中两个凸紧集的Ｄｅｍｙａｎｏｖ差推广到犚犿×狀空间．借助于这种差，建立了Ｃｌａｒｋｅ广义Ｊａｃｏｂｉ与拟微分的关系，从而给出了利用拟微分计算Ｃｌａｒｋｅ广义Ｊａｃｏｂｉ的方法．对于两个有限点集凸包给出了它们Ｄｅｍｙａｎｏｖ差的具体表达式．最后讨论了在求解非光滑方程组中的应用．     

计算几何中几何偏微分方程的构造

平均曲率流、曲面扩散流和Willmore流等著名的几何流除了在理论方面有重要的意义之外,在计算机辅助几何设计、计算机图形学以及图像处理等领域也得到了广泛的应用．然而在解决实际问题时,人们经常要根据问题的特点构造其它具有指定性质的几何流．本文从统一的观点出发,对于参数曲面以及水平集曲面,给出了几类重要几何偏微分方程(包括L2梯度流、H-1梯度流以及H-2梯度流)的构造．这几类几何流的包容十分广泛,上述提到的几个几何流均为其特例．     

双会议服务器选址问题研究

中位选址问题一直是管理学科的研究热点,本文考虑平面点集选址问题中的双会议服务器选址问题,该问题可以看成是2中位问题的衍生问题。令P为平面上包含n个点的点集,双会议服务器选址问题即为寻找由该点集构成的一棵二星树,使得这棵树上所有叶子之间的距离和最小。本文给出求解该问题的关键几何结构和最优解算法设计,并证明所给算法时间复杂性为O(n³logn)。     

单位球面S~(n-1)上球凸集的分析研究方法（英文）

本文研究了欧式空间单位球面S~(n-1)上秋凸集的定义与基本性质.利用径向函数,定义了空间中有限个点的凸组合运算,并由此给出了S~(n-1)上球凸集的分析定义和集合球凸包的定义.讨论了球凸集和球凸包的基础性质.最后证明了任一闭球凸集都可以表示为其端点集的球凸包.这个结论的形成与获证完全得益于本文采用的分析方法.     

常曲率空间中有限点集的两类几何不等式

应用距离几何的理论与方法,研究了n维常曲率空间中有限点集的一些几何度量之间关系,建立了常曲率空间中有限点集的两类几何不等式,推广了已有的结果.     

一元非线性系统的BP算法研究

详细研究了一种一元非线性系统的BP算法,提出并证明了该算法的收敛性定理,给出了该算法的应用实例.计算机仿真结果表明:对于随机给定的初始点,该算法都能稳定收敛到它的一个实根,而且计算精度可控,因此,该算法是有效的.与传统的计算方法相比,本文算法不仅具有收敛速度快,而且计算精度可控以及初始点随机给定的集中优点.     

Clifford 代数,几何计算和几何推理

Clifford代数是一种深深根植于几何学之中的代数系统,被它的创始人称为几何代数．历史上,E．Cartan,R．Brauer,H．Weyl,C．Chevalley等数学大师都曾研究和应用过Clifford代数,对它的发展起了重要作用．近年来,Clifford代数在微分几何、理论物理、经典分析等方面取得了辉煌的成就,是现代理论数学和物理的一个核心工具,并在现代科技的各个领域,如机器人学、信号处理、计算机视觉、计算生物学、量子计算等方面有广泛的应用．本文主要介绍Clifford代数在几何计算和几何推理中的应用．作为一种优秀的描述和计算几何问题的代数语言,Clifford代数对于几何体,几何关系和几何变换有不依赖于坐标的、易于计算的多种表示,因而应用它进行几何自动推理,不仅使困难定理的证明往往变得极为简单,而且能够解决一些著名的公开问题,目前在国际上,几何自动推理已经成为Clifford代数的一个重要应用领域。     

一个经典不等式的高维推广

§1 引言本世纪二十年代,一门新的几何学分支诞生了,这就是由K.Menger开创的距离几何.L.M.Blumenthal的专著《Theory and Applications of Distance Geometry》集三、四十年代距离几何研究成果之精华使之成为一本距离几何的经典著作.距离几何不仅自身充满了浓郁的理论趣味,而且还有着广泛的实际应用价值.近年来距离几何越来越引起国际国内科学家们的注意,并在分子生物化学、统计学、理论物理学等方面得到了应用.本文运用距离几何的方法把一个经典的几何不等式作了高维的推广. 对于欧氏空间中的点集{P_1,P_2,…P_N},一动点P到它们距离的平方和     

微分多项式系统的约化算法理论

本文中，作者推广了纯代数形式的特征列集理论（吴方法）为微分形式的相应理论，即建立了在机器证明了诸多微分问题中非常重要的微分多项式组的约化算法理论。引入了一些新的概念和观点使函数微分（导数）具有直观的代数几何表示。给出了Coherent条件下的特征列集的算法。给出的算法易于在计算机上实现并适合应用于广泛的微分问题，如微分方程对称计算，各种微分关系的自动推理等问题。     

函数分段有理二次Bézier插值与逼近

依据几何特征对函数进行合理分段,定义了函数的分段三角形凸包,给出了控制多边形的确定方案,详细地讨论了函数的分段有理二次Bézier插值算法.定义了一种便于计算的新型误差,在此误差意义之下,插值算法的精度高于已有的逼近算法.数值实验结果表明了算法的可行性和有效性.     

SIFT算法在图像拼接中的应用研究

SIFT算法在计算机视觉中具有广泛的应用,SIFT是一种稳定的图像局部特征匹配算法,该算法具有非常高的唯一性和稳健性,对于图像的亮度变化、尺度缩放、旋转变化和噪声等具有很好的鲁棒性.通过研究SIFT算法的基本原理和步骤,利用pycharm-community-2019.3.2开发工具、python3.7.9对SIFT算...     

(3,3,1,1)层次B样条与分级T网格上多项式样条的相互转换

1引言 B样条在计算机图形学和几何建模等领域有着广泛的应用[3,8].在应用过程中,通常都需要对得到的模型进行修改以到达更好的效果.对于B样条曲线,利用节点插入算法可以有效地进行局部修改.     

蒙特卡罗计算点通量的二次碰撞概率方法和重要抽样方法

1.引言 应用蒙特卡罗方法计算点通量,在粒子输运问题中占有非常重要的地位。首先,是由于点通量的计算问题在实际问题中经常遇到;其次,是由于任何局部通量计算问题均可通过点通量的计算实现;最后,是由于用其他数值方法计算点通量存在一点困难,尤其是对于那些几何以及其他因素复杂的问题更是如此。     

最小最大二点集覆盖问题分析及改进算法设计

本文考虑二中心问题的扩展问题-最小最大二点集覆盖问题。给定两个平面点集P₁和P₂,分别包含m和n个点,求两个圆分别覆盖P₁和P₂,并且要求两圆半径与两圆圆心距三者中的最大值最小。本文主要贡献在于分析半径变化过程中两个点集中心包之间最近距离的变化关系,其中中心包是点集所具有的一个特殊几何结构,所得到的结果改进了Huang等人之前给出的结果,并且通过该结果设计相应算法,所得到的算法复杂性是目前最好的。     

混料凸多面体顶点的分枝构造法及修正的CONSIM算法

的利益区域的几何解释都是(q-1)维空间正规单纯形内的凸多面体.对于利益区域(1)或(2),当采用一阶或二阶混料回归多项式作为回归模型时,由Elving,Snee与Mar-quardt、Snee的结论可知,最优设计的第一步是求出混料凸多面体(1)或(2)的极端顶点,因为混料凸多面体的棱中点、面中心及总体中心都是顶点集合中某个顶点子集的中