三次有理Bézier曲线的形状调整方法

给出了两类调整三次有理Bézier曲线形状的方法。一类方法是使曲线通过给定的插值点,从而实现曲线的形状调整。另一类方法是将曲线上的点作为控制多边形两边连线段上的分点,通过调整分线段的比例,实现对曲线的形状调整。针对不同情况,分别给出了权因子的计算公式。计算方法简单,使用方便,并使三次有理Bézier曲线的形状调整更加具体和明确。同时,由计算结果得到了任意三次有理Bézier曲线不相交的充分必要条件。     

带权混合支配问题的近似算法研究

图G=(V,E)上的混合支配集D是由图G中的顶点和边组成的集合,因此对于图G中的任意一条边或一个顶点,若其不在D中,则其必须与D中某条边或某个顶点相邻。混合支配问题是在一个图中找到一个基数最小的混合支配集。混合支配问题是图顶点支配问题和边支配问题的混合,在实际生活中有着许多应用,最近在算法中也备受关注。混合支配问题在一般图上是NP完全的。带权混合支配问题则是混合支配问题的一个自然推广,其将图中的点和边以不同权重进行区分。令图中所有点的权重均为w_v,所有边的权重均为w_e,带权混合支配问题则要求寻找一个混合支配集使得其点和边的权重之和达到最小。尽管针对混合支配问题已存在一个简单2倍近似算法,但是对带权混合支配问题的近似算法的研究进展却非常缓慢。在点的权重不大于边的权重的情况下,文中给出了带权混合支配问题的一个3倍近似算法。     

低度图的点覆盖和独立集问题下界改进

给出了一种提高低度图点覆盖和独立集问题下界的精确算法．通过分析如何有效地减少图中的顶点来打破原问题的NP-Hard结构建立起搜索递推关系；得出3度图的最小点覆盖问题的解决时间为O(1．1033^n)，参数化的3度图点覆盖问题的解决时间为O(kn 1．2174^k)；将此算法应用到3度图的最大独立集问题上，可以得到运行时间为O(1．1033^n)的解．以上3结果均打破原有最佳下界。     

有理Bézier曲线权因子的有效形式

给出了确定 n 次有理 Bézier 曲线权因子的权系数极大化方法和幂指数型权因子方法。这些方法根据 Bernstein 基函数及其系数来选取权因子。系数极大化方法表示的曲线是一种确定的适合于任意次数的有理 Bézier 曲线,它可以比 Bézier 曲线更好地保持其控制多边形的形状。幂指数型权因子方法给出了有理 Bézier 曲线权因子的有效形式。它既保持了一般有理权因子的局部可调性,又能使形状调整的效果更明显。     

负参数Bézier曲线的性质及其应用

1引言 从便于形状处理、形状信息传递与数据交换的角度来看,形状的数据描述应满足如下要求[1,2]:1.唯一性;2.同一形式性;3.几何不变性;4.易于定界性.在实际应用中往往难以做到的是3、4条.Bezier曲线则利用了Bernstein基函数和等于1来满足几何不变性,再又利用各基函数非负来达到凸包性.易于定界不一定要是凸包的,文[2]中就负权因子分析了这种丧失了凸包性的有理二次Bezier曲线的一些性质,得出用不同的负权因子来生成椭圆弧、抛物线弧和双曲线弧的应用.     

带有多折扣选项的滑雪租赁问题的在线和离线算法

研究了带有多折扣选项的滑雪租赁问题（ski-rental problem with multiple discount options,简称多折扣租赁问题）的离线和在线算法.多折扣租赁问题是经典的滑雪租赁问题的一个自然扩展,在现实生活中有着非常广泛的应用.在多折扣租赁问题中,除了租借一次装备和购买滑雪装备的选项以外,还存在多次租借装备的选项,这种多次租借可以得到折扣.一次租借次数越多,折扣就越大.规则价格子问题则是多折扣租赁问题中要求各选项的价格成倍数关系的一类子问题.证明了多折扣租赁问题的离线问题是NP难的,但对于规则价格子问题的离线问题,给出了一种线性时间算法.基于对离线问题的算法分析,给出了规则价格子问题的一个2倍竞争比的在线策略,同时证明了该问题的最优竞争比是2.基于规则价格子问题的在线策略,又给出了多折扣租赁问题的一个新的4倍竞争比的在线策略,该竞争比同样达到了最优.最后,通过对现实生活中的数据和随机数据进行实验,说明所给出的在线算法具有实际应用价值.