圆弧和直线段组成的封闭曲线凸凹性快速判定

首先通过构造一中介凸多边形求出封闭曲线的方向，然后根据封闭曲线方向确定顶点及圆弧的凸凹性，进而确定封闭曲线的凸凹性．文中算法快速稳定，其时间复杂度为O(n)，计算量最多为15n 33k 25次判断、12n-6k 14次乘除法、10n 16k 21次加减法、2次求正余弦和k次开方运算，其中n为封闭曲线顶点和圆弧圆心的个数、k为圆弧个数．     

多边形链求交的改进算法

多边形链求交是CAD&CG及相关领域研究中的一个基本问题 利用多边形链的凸凹性、单调性等特性 ,结合包围盒技术 ,在扫描线算法基础上 ,提出一种多边形链求交的改进算法 该算法特别适用于包含大量直线段且交点数相对于顶点数少得多的多边形链求交的情况     

B样条曲线同时插入多个节点的快速算法

基于离散B样条的一个新的递推公式，提出B样条曲线同时插入多个节点的新算法。不同于Cohen等插入节点的Oslo算法，本算法用新的方法离算离散B样条，求每个离散B样条的值只需O(1)的运算量，从而使本算法高效，其时间复杂性为O(sk n)，其中k为B样条曲线的阶，n k 1为原节点数，s为新插入节点的个数,本算法的通用性强，适用于端点插值的和非端点插值的B样条曲线，可同时在曲线定义域内外的任意位置上插入任意个节点。     

用最小回路求两个简单多边形的交、并、差集

针对求两个简单多边形交、并、差集问题,提出一种基于最小回路的新算法。首先,将初始多边形P和Q初始化为逆时针方向,并将两个多边形交点处的关联边排序。然后,从各个交点出发利用最小转角法搜索最小回路,并根据这些最小回路中包含P和Q边的方向性对它们进行分类。最终,不同类别的最小回路将对应P和Q的交、并、差集。算法的时间复杂度为O((n+m+k)logd),其中n、m 分别是P和Q的顶点数,k是两多边形的交点数,d为将多边形分割的单调链数。算法几何意义明显,对于多边形布尔运算中的重合顶点、重合边等奇异情形,具有较好的适应性。     

若干二元周期序列的紧错线性复杂度

综合线性复杂度、k错线性复杂度、k错线性复杂度曲线和最小错误minerror（S）的概念,提出m紧错线性复杂度的概念。 序列S的m紧错线性复杂度是一个二元组（km,LCm）。序列S的k错线性复杂度曲线的第m个跃变点对应的km值和对应km错线性复杂度LCm,称为序列S的m紧错线性复杂度。通过使用简洁的cost二维结构,给出了周期为2n的二元序列的紧错线性复杂度算法,并证明具有Stamp-Martin模式的线性复杂度算法均可以简单地推广为求紧错线性复杂度的算法。与现有k错线性复杂度算法不同,该算法中省去了原来序列元素的运算。在王-张-肖算法基础上,通过使用cost二维结构,给出了周期为pn的二元序列的紧错线性复杂度算法,其中p是一个素数,2是一个模p2的本原根。     

结合多目标优化算法的模糊聚类有效性指标及应用

模糊聚类方法可以更有效地对复杂数据集进行分析,由于模糊聚类算法的种类繁多且聚类结果会随着输入的聚类个数的不同而改变,使得模糊聚类算法产生的结果不准确,因此,要获得准确的聚类结果必须确定模糊聚类个数k.目前已有的研究主要是利用多种模糊聚类有效性指标来确定最优聚类个数k,但是诸如SSD,PBM等模糊聚类指标会随着划分的聚类个数k的增加而单调递减,导致聚类个数k不准确.为此,文中提出了一种结合多目标优化算法的模糊聚类有效性指标(A Validity Index of Fuzzy Clustering Combined with Multi-obj ective Optimization Algorithm,OSACF),将模糊聚类度量指标与多目标优化算法(Multi-Obj ective Optimization Algorithm,MOEA)相结合来解决聚类最优个数k的问题.与使用聚类有效性指标不同,OSACF通过建立聚类个数k与聚类度量指标之间的双目标模型并使用MOEA优化该双目标模型来确定最优聚类个数k,避免了聚类有效性指标趋于单调递减的影响.另一方面,OSACF使用形态形似距离替代传统的欧氏距离度量,避免了聚类形状对计算聚类k值的影响.实验结果表明,OSACF结合MOEA得到的最优模糊聚类个数k比已有的聚类有效性指标获得的结果更准确.     

快速动态优先搜索树的实现及其应用

对形如（x1：x2,[-∞：y]）的二维查询问题,提出一种快速的、易于实现的动态优先搜索树数据结构及其相关算法,采用只在叶节点存储数据的结构,以及在常数时间内实现旋转操作的算法。设n为数据点的个数,k为满足搜索条件的解的个数,则该动态搜索树空间复杂度为O（n）,插入、删除操作的时间复杂度为O（10gn）,搜索复杂度为O（logn＋k）。     

Con／k／n：F系统单元序列最优化的模拟退火算法

n中取链续k(con/k/n:F)系统单元序列最优化的实质是一个组合优化问题，该文设计了求解任意con/k/n:F系统全局最优配置的模拟退火算法，并以计算实例检验了该算法。     

适用于网络渐进传输的多分辨率曲线生成算法

针对渐进传输系统在多分辨率矢量数据生成过程中存在的计算费时、拓扑不一致问题,提出一种适用于网络渐进传输的多分辨率曲线生成算法。该算法通过预先存储的节点偏离量化简曲线,利用优化的单调链求交算法维护曲线拓扑一致性,从而支持多分辨率曲线的快速生成和拓扑一致性维护。基于该算法开发了曲线数据渐进传输实验系统,实验结果表明,多分辨率曲线数据保持了拓扑一致性,且其生成时间与数据量大小呈近线性的关系,证明了算法的有效性。     

计算SKY的预排序分组算法

在SFS算法的预排序思想基础上,借助数据集R上的单调分值函数,将R的点分组,提出计算Skyline的迭代算法。算法有效地支持用户的偏爱。给出证明：若R的点的个数为n,R的Skyline的点的个数为m,则在计算R的Skyline的过程中,需要对点之间所做的支配比较的次数不超过m(n-m/2-1/2);如果分组的组数为k,则分组算法比SFS减少比较次数不少于m(m-k)/2k。     

Reporting Red—Blue Intersections between Two Sets of Connected Line Segments

Abstract. We present a new line sweep algorithm, HEAPSWEEP, for reporting bichromatic (``purple') intersections between a red and a blue family of line segments. If the union of the segments in each family is connected as a point set, HEAPSWEEP reports all k purple intersections in time O((n+k) α(n) log ³ n) , where n is the total number of input segments and α(n) is the nearly constant inverse Ackermann function. To achieve these bounds, the algorithm maintains only partial information about the vertical ordering between curves of the same color, using a new data structure called a kinetic queue . In order to analyze the running time of HEAPSWEEP, we also show that a simple polygon containing a set of n line segments can be partitioned into monotone regions by a set of vertical threads cutting these segments O(n log n) times.     

3-Dimensional curve similarity using string matching

In this paper, we present a new approach to measuring the similarity between 3D-curves. Our approach allows the possibility of using strings, where each element is a vector rather than just a symbol. We present two different approaches for representing 3D-curves. One possibility is to represent a 3D-curve as two 2D-curves, one being the projection of the 3D-curve in the XY-plane, and the other one in the YZ-plane. For the case that we need geometric rotation invariance, we have used a second approach to the symbolic representation of the 3D-curve using the curvature and the tension as their symbolic representation. We validate this approach through experiments using synthetic and digitalized data.     

Offset tool-path linking for pocket machining

For die-cavity pocketing, contour-parallel offset (CPO) machining is the most popular machining strategy. CPO tool-path generation for pocketing includes geometrical and technological issues: (1) a 2D-curve offsetting algorithm; and (2) optimizing technological objectives, such as tool-path linking. The 2D-curve offsetting solution has been widely studied, because it has so many potential applications. However, though the tool-path linking may seriously affect the machining performance, there have been few reported investigations on optimizing the CPO tool-path linking. This paper presents a CPO tool-path linking procedure optimizing technological objectives, such as dealing with islands (positive and negative) and minimizing tool retractions, drilling holes and slotting. Main features of the proposed algorithm are as follows: (1) a data structure, called a ‘TPE-net’, is devised to provide information on the parent/child relationships among the tool-path-elements; (2) the number of tool retractions is minimized by a ‘tool-path-element linking algorithm’ finding a tour through the TPE-net; and (3) the number of drilling holes is minimized by making use of the concept of the ‘free space’ (negative islands or already machined region).     

基于矩形包围盒的多边形碰撞检测算法

碰撞检测是计算机图形学领域中的一个普遍存在的问题。为了提高多边形碰撞检测的效率 ,针对简单形式刚性运动的多边形对象 ,提出了一种基于二维轴向矩形包围盒结构的平面简单多边形碰撞检测算法。该算法基于坐标轴的单调性对多边形进行分割 ,并通过矩形包围盒之间的预检来减少无关边对的相交测试 ,以加速算法的终止。由于采用轴向扫描线方法可以大大减少包围盒测试的数量和线段求交的数量 ,所以 ,经过少量的“边 -边”相交判断就能求解到所有交点 ,同时能快速地获得两多边形干涉发生的第 1位置。试验表明 :(1)对于一般多边形 ,该算法的复杂度也远远低于 O(NP× NQ) ;(2 )对于凸多边形对象 ,该算法的复杂度为 O(NP NQ) ,其中 NP,NQ 为多边形 P,Q的顶点数。由此可见 ,算法能够获得较好的运算效率     

折线链节点标注技术

针对传统多边形位置关系计算比较烦琐,以及简单多边形的理论难以拓展到一般多边形的问题,提出标注节点状态的方法.通过定义11种位置来描述折线链上每个节点的状态,再采用"线段端点与线段"和"线段端点与邻折线"的标注方法来实现任意折线链的标注,同时利用两线段分割预处理使相交仅发生在端点处,从而使算法更高效;然后给出折线链基本位置关系的节点特征,并且探讨了三维顶点的标注方法.该方法的标注原理简单、方法实用,算法空间和时间复杂度分别为O(n)和O(n2).实验结果表明,该方法对任意形状的折线链都能实现稳定标注;通过搜索节点状态特征可以求解折线链间的相互关系,还可以实现一般折线链的碰撞检测、相交区域计算以及多边形简单化分解等.     

On the capabilities of higher-order neurons: a radial basis function approach

Higher-order neurons with k monomials in n variables are shown to have Vapnik-Chervonenkis (VC) dimension at least nk + 1. This result supersedes the previously known lower bound obtained via k-term monotone disjunctive normal form (DNF) formulas. Moreover, it implies that the VC dimension of higher-order neurons with k monomials is strictly larger than the VC dimension of k-term monotone DNF. The result is achieved by introducing an exponential approach that employs gaussian radial basis function neural networks for obtaining classifications of points in terms of higher-order neurons.     

一类扩展的Steiner树优化问题及其应用

本文提出了一个计算机网络通信和分布式系统中的一类扩展的Ｓｔｅｉｎｅｒ树问题．对此问题设计了两个求其最优解的算法．这两个算法的时间复杂性分别是Ｏ（３（ｋ－１）·ｎ＋２（ｋ－１）·ｎ２）和Ｏ（２（ｎ－ｋ）·ｎ２）．其中，ｋ是一棵Ｓｔｅｉｎｅｒ树需支撑的给定顶点的个数．     

Finding Pathway Structures in Protein Interaction Networks

The increased availability of data describing biological interactions provides important clues on how complex chains of genes and proteins interact with each other. Most previous approaches either restrict their attention to analyzing simple substructures such as paths or trees in these graphs, or use heuristics that do not provide performance guarantees when general substructures are analyzed. We investigate a formulation to model pathway structures directly and give a probabilistic algorithm to find an optimal path structure in time and space, where n and m are respectively the number of vertices and the number of edges in the given network, k is the number of vertices in the path structure, and t is the maximum number of vertices (i.e., "width") at each level of the structure. Even for the case t = 1 which corresponds to finding simple paths of length k, our time complexity is a significant improvement over previous probabilistic approaches. To allow for the analysis of multiple pathway structures, we further consider a variant of the algorithm that provides probabilistic guarantees for the top suboptimal path structures with a slight increase in time and space. We show that our algorithm can identify pathway structures with high sensitivity by applying it to protein interaction networks in the DIP database.     

Enumeration of linear threshold functions from the lattice of hyperplane intersections.

We present a method for enumerating linear threshold functions of n-dimensional binary inputs, for neural nets. Our starting point is the geometric lattice L(n) of hyperplane intersections in the dual (weight) space. We show how the hyperoctahedral group O(n+1), the symmetry group of the (n+1)-dimensional hypercube, can be used to construct a symmetry-adapted poset of hyperplane intersections Delta (n) which is much more compact and tractable than L(n). A generalized Zeta function and its inverse, the generalized Mobius function, are defined on Delta(n). Symmetry-adapted posets of hyperplane intersections for three-, four-, and five-dimensional inputs are constructed and the number of linear threshold functions is computed from the generalized Mobius function. Finally, we show how equivalence classes of linear threshold functions are enumerated by unfolding the symmetry-adapted poset of hyperplane intersections into a symmetry-adapted face poset. It is hoped that our construction will lead to ways of placing asymptotic bounds on the number of equivalence classes of linear threshold functions.