双自由度三次参数样条

近年来,在计算机辅助几何设计中,参数样条对曲线的拟合越来越显得重要了。这方面的部分工作可见[1—7]。本文限于讨论平面上曲线的拟合问题。 如图一,给定两点P_0,P_1以及曲线在这两点的速度向量V_0,V_1,用P_0,P_1,λV_0,     

一般欧氏空间点集凸包的快速实时算法

点集凸包算法是被Shmaos等称之为计算几何中的基本问题之一,这是由于它在计算机辅助设计、计算机图形学、模式识别和运筹学等领域中有着十分广泛的应用。 对于2、3维凸包算法的研究已有许多成果,给出了各种不同意义下的最佳算法(参见[2])。但是对于高维空间点集凸包算法的研究却甚少,目前只有两种算法在计算几何中得到应用。造成这种局面的因素乃是高维空间的抽象性质,缺少2,3维空间的那种几     

三个点的加权点组的费马问题

平面上三个点的加权点组的费马问题是 :A、B、C是平面上三个定点 ,设 a′、b′、c′是非负实数 ,在平面上试求点 P,使F =a′ PA b′ PB c′ PC为最小 .当 a′=b′=c′=1时即为法国数学家费马 ( Fermat,1 6 0 1～ 1 6 6 5)于 1 6 40年前后向意大利物理学家托里拆里 ( Torricelli,1 6 0 8～1 6 47)提出的问题 ,通常被人们称之为平面上给定三点的费马问题 .对于平面上三个点的加权点组的费马问题 ,人们有过许多研究 ,可参阅文献 [1 ]～[4 ],但据笔者所知 ,其结论多用模拟力学机构给以说明 ,未见到纯几何解答 .在本文中 ,笔者用纯几何…     

共线点与共点线问题的研究

利用向量法、坐标法、仿射变换以及射影几何中的德萨格定理、帕斯卡定理和布利安桑定理,解决初等几何中的共线点和共点线问题.     

多动点轨迹问题处理策略

轨迹问题中,如果涉及的动点数目不只一个,我们称之为多动点轨迹问题。本文谈谈该类题目的处理思路。 1 运用几何性质 利用图形的几何性质,由形思数、把形与数恰如其分地结合起来,常能避繁就简、化难为易。 例1 直角三角形ABC中,∠C是直角,     

用几何画板证“五点共圆”

本刊2001年3月(上)期,周春荔先生的文章介绍了“五点共圆”[1]问题,并给出了几何证明.该题的证明确实有一定难度.但是,若利用《几何画板》这个软件中的度量功能证明,就再简单不过了. 证明过程如下: 先作出符合题意的图形.     

三角形的十八点共圆定理

在近代欧氏几何关于三角形的多点共圆定理中,三角形的九点圆定理大概算是人们最熟悉的了.而在1901年由杜洛斯-凡利(Droz-Farny)发现的三角形十二点共圆定理[1],则可能并不为人们所熟悉.     

中考题中的调和点列

1.调和点列的概念和性质。定义1^[1]如图1,对于线段AB的内分点C与外分点D,若AC/CB=AD/DB,则称C、D调和分割线段AB(或线段AB被C、D调和分割),或称点列A、B、C、D为调和点列.在射影几何中,①式写成AC·AD/BC·BD=-1(AC·AD/BC·BD称为点列A、B、C、D的交比,记为(AB,CD)).     

点和它的对偶直线在解题中的妙用

<正>1问题的提出极点极线(特殊的点和直线的对偶关系)是高等几何的概念,二次曲线的好多性质都与它有关,许多考题的设计也都来源于此,虽然以前也有好多论述,但好多师生并不熟悉,本文再次加以总结,希望对读者有所帮助.文[1]论证了圆锥曲线内的点和它的对偶直线的存在性和对应关系,得到了关于对偶点     

关于S-正则语言类的两点注记

文献[1]引入和研究了S-正则语言及其语言类的代数结构.本文作为对[1]的两点注记,讨论了S-正则语言类与语言的Chomsky层次之间的关系,以及上的等价关系≈.     

定义域曲面上光滑插值方法

1　引　　言限制在光滑曲面的函数插值是计算几何中一个较新研究方向 ,有广泛的应用前景 .如飞机机翼上压力估算 ;人体表面的温度分布 ;分析地球上的降雨量以及大气层的“温室效应”,包括臭氧层的估计等 .目前 ,已有一些解决它的方法 ,其中大部分方法是构造球面上插值函数[1 ,2 ,3 ] ,主要思想是用大圆弧代替直线段 ,从而将欧氏空间中已有的插值方法推广到球面上构造插值函数 ,这种方法最大的缺陷是难以推广到一般的曲面上 ,因一般曲面上两点间测地线不易求出 .还有一些方法 [4,5,6] 是基于曲面的三角或四面体划分 ,有相对多得多的插值函数…     

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

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

由算法分析引出的一类差分方程的解及其相应的求和公式——悼念游兆永教授

感谢会议对我的邀请并提供发言的机会，此时此地，此会此际，本来游兆永教授当应居东道的首席，不幸不久前逝世了，令人不胜悲痛和惆怅。     

B样条基转换矩阵的解析表示和计算公式

摘要B样条基的转换矩阵具有重要的理论和应用意义。本文研究其最基本的问题：存在性条件、解析表示和计算方法，利用差商展开系数得到了上述问题的有关结果，本文的结果为CAGD中B样条曲线的节点插入、节点删除、升阶、降阶、分割、组合等重要技术提供了一个统一的数学背景和实现方法。     

求解一类非单调线性互补问题的路径跟踪法及其计算复杂性

１．引言及记号 线性互补问题的一般形式是;求（ｘ,ｓ） 　　　　　　　 使其中 众所周知,当Ω＋非空时,单调线性互补问题可在多项式时间内求解,而且人们已经设计出了多种求解单调线性互补问题的有效的内点算法（见［１］和［７］）．然而,对于求解非单调线性互补问题的内点算法的研究可以说才刚刚开始．文［２］讨论了当Ｍ为Ｐ矩阵时问题（１）的中心路径的存在唯一性;文［３］给出了设计求解一类非单调线性互补问题的内点算法的一般框架;文［４］给出了求解一类非单调线性互补问题的一种势能函数约减法并讨论了其算法的计算复杂…     

Representing Utility Functions via Weighted Goals

We analyze the expressivity, succinctness, and complexity of a family of languages based on weighted propositional formulas for the representation of utility functions. The central idea underlying this form of preference modeling is to associate numerical weights with goals specified in terms of propositional formulas, and to compute the utility value of an alternative as the sum of the weights of the goals it satisfies. We define a large number of representation languages based on this idea, each characterized by a set of restrictions on the syntax of formulas and the range of weights. Our aims are threefold. First, for each language we try to identify the class of utility functions it can express. Second, when different languages can express the same class of utility functions, one may allow for a more succinct representation than another. Therefore, we analyze the relative succinctness of languages. Third, for each language we study the computational complexity of the problem of finding the most preferred alternative given a utility function expressed in that language (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Monte Carlo methods in applied mathematics and computational aerodynamics

A survey of the Monte Carlo methods developed in the computational aerodynamics of rarefied gases is given, and application of these methods in unconventional fields is described. A short history of these methods is presented, and their advantages and drawbacks are discussed. A relationship of the direct statistical simulation of aerodynamical processes with the solution of kinetic equations is established; it is shown that the modern stage of the development of computational methods is impossible without the use of the complex approach to the development of algorithms with regard for all the specific features of the problem to be solved (its physical nature, mathematical model, the theory of computational mathematics, and stochastic processes). Possible directions of the development of the statistical simulation methods are discussed.     

A computational method for a class of optimal relaxed control problems

In the present paper, we propose a computational scheme for solving a class of optimal relaxed control problems, using the concept of control parametrization. Furthermore, some important convergence properties of the proposed computational scheme are investigated. For illustration, a numerical example is also included.     

A Sausage Heuristic for Steiner Minimal Trees in Three-Dimensional Euclidean Space

Given a set V of size N≥4 vertices in a metric space, how can one interconnect them with the possible use of a set S of size M vertices not in the set V, but in the same metric space, so that the cumulative cost of the inter-connections between all the vertices is a minimum? When one uses the Euclidean metric to compute these inter-connections, this is referred to as the Euclidean Steiner Minimal Tree Problem. This is an NP-hard problem. The Steiner Ratio ρ of a vertex set is the length of this Steiner Minimal Tree (SMT), divided by the length of the Minimum Spanning Tree (MST), and is a popular and tractable measure of solution quality.The ?-Sausage heuristic described in this paper employs a decomposition technique to explore the point set. The fixed vertices of the set are connected to a set of centroid vertices of Delaunay tetrahedrons. The path topology is preserved as far as possible, together with a cycle prevention rule, where junctions, and deviations from the ?-Sausage structure occur. Furthermore, repeated sweeps, with different root vertices are accommodated.The computational complexity of the heuristic is shown to be O(N²). Experimental results with thousands of vertices are presented. Comparisons with an exponential running time Branch and Bound algorithm are also shown.     

一类非单调线性互补问题的高阶Dikin型仿射尺度算法

对于一类非单调线性互补问题提出了一个新算法：高阶Dikin型仿射尺度算法，算法的每步迭代．基于线性规划Dikin原始-对偶算法思想来求解一个线性方程组得到迭代方向，再适当选取步长，得到了算法的多项式复杂性。