Computational Geometry lecture notes1-2

基于射线管分裂方法的SAR场景快速消隐技术董纯柱;殷红成;王超【摘要】SAR场景模型常采用非均匀三角网格描述，使得传统的基于Z-Buffer技术的消隐算法难以在保持较高的消隐精度的同时兼顾消隐效率。

该文提出了一种基于射线管分裂方法的 SAR 场景快速消隐技术，将复杂 SAR 场景的消隐问题分解为两个简单过程：一是对场景三角网格在发射平面上的投影点云做2维Delaunay 三角网格划分，二是基于射线管分裂方法对新生网格可见性进行判断和拓扑重构。

典型飞机目标和草地上T-72坦克的消隐结果验证了该方法的准确性和高效性。

% Traditional hidden surface removal algorithm based on hardware Z-Buffer technique cannot give attention to precision or efficiency at the same time when dealing with the non-uniform triangulated SAR (Synthetic Aperture Radar) scene model. A novel high-precision hidden surface removal approach using fast ray-tube splitting algorithm is proposed, where the SAR scene hidden surface removal problem is decomposed into two simple procedures, i.e. a Delaunay triangulator is used to generate the initial ray tubes from the projected point clouds of all incident visible vertices, then an adaptive ray-tube splitting method is adopted to carry out the complex scene shading situations and resultant visible model reconstruction. Simulation results of typical aircraft and T-72 tank show that, the new approach is feasible and effective.【期刊名称】《雷达学报》【年(卷),期】2012(000)004【总页数】5页(P436-440)【关键词】消隐算法;射线管分裂方法;Delaunay三角剖分;Z-Buffer算法;SAR场景【作者】董纯柱;殷红成;王超【作者单位】中国传媒大学信息工程学院北京 100024; 电磁散射重点实验室北京100854;中国传媒大学信息工程学院北京 100024; 电磁散射重点实验室北京100854;电磁散射重点实验室北京 100854【正文语种】中文【中图分类】TN957对基于模板匹配的SAR图像解译而言，SAR图像中特有的透视收缩、叠掩和阴影等几何畸变特性是重要且稳定的识别特征[1]。

利用对称性求最小值问题唐乐红【摘要】Secure multi-party computation has been more and more widely used in many fields.It has become one of the hot issues in information security field.Privacy-Preserving Computational Geometry ( PPCG) is a spe-cial kind of secure multi-party computation problem.By using existing scalar product protocol, we propose a new protocol by using symmetry to solve the minimum value problem, and furthermore analyze the correctness, secur-ity and complexity performance of the protocol.%安全多方计算问题，在很多领域得到了越来越广泛的应用，已成为信息安全领域的研究热点之一。

保护私有信息的计算几何问题，是一类特殊的安全多方计算问题。

利用点积协议，提出了关于利用对称性求最小值问题的保密协议，并分析了协议的正确性、安全性和复杂性。

【期刊名称】《兰州工业学院学报》【年(卷),期】2015(000)001【总页数】3页(P56-58)【关键词】安全多方计算;计算几何;点积协议;最小值问题【作者】唐乐红【作者单位】福州大学阳光学院，福建福州 350015【正文语种】中文【中图分类】TP309所谓的安全多方计算(Secure Multi-party Computation，SMC)，是指在一个分布式网络中，在各参与方互相不信任的情况下，能够在保护各参与方输入信息隐私的同时，协同合作完成一定的任务.SMC在很多领域得到了越来越广泛的应用.保护私有信息的计算几何问题(Privacy-Preserving Computational Geometry，PPCG)是指在分布式网络环境中，对参与者各自输入信息保密的前提下，使得所有参与者通过合作完成某项计算几何问题.例如：A、B两个开发商想共同合作开发某个区域，但又不希望在施工前向对方泄露自己的计划,如何在保护各自计划的条件下，求出A的两个施工地点与B的施工路线之间的最小距离.此时，我们可以把施工地点抽象成1 个点，施工线路抽象成1 条线[1].这个问题可以转化为求一条直线上的动点与两定点之间的最小值问题.本文所设计的协议，前提是假定双方的计算环境是安全的,通过利用已有的点积协议，提出了利用对称性保密求一条直线上的动点与两定点之间的最小值问题.整个计算过程要求双方严格执行协议规程，这就是通常所说的半诚实.安全点积协议[2]现已成为安全多方计算SMC中的一个重要基础协议，在SMC中有着广泛的应用.安全点积协议可以形式化地描述为：Alice拥有一个私有向量X=(x 1,x2,…,xn)，Bob 则拥有另一个私有向量Y=(y1,y2,…,yn)，双方希望在不向对方透露各自私有数据的情况下，通过协作计算获得点积结果xiyi.不经意传输协议(Oblivious Transfer，OT)[3]，是一种可以保护双方隐私的通信协议.此协议是一个由发送方A和接收方B共同参与的双方通信协议.基本思路为：发送方A发出m1,m2,...,mn的n条消息，执行协议后接收方B将得到其中的一条或几条消息.发送方A不能控制接收方B的选择，也不知道接收方B收到的是哪一条或哪几条消息，而接收方B不能得到其选择之外的信息.输入：Alice拥有数据X=(x1,x2,…,xn)，Bob拥有数据Y=(y1,y2,…,yn).输出：Alice获得X·Y+v，其中v是Bob选取的随机数.执行过程：1) Alice和Bob事先协商好两个数p和m,能使得pm足够大.2) Alice生成任意m个随机向量V1,…,Vm，并且满足.3) Bob生成任意m个数r1,…,rm,使其满足4) 对每个j=1,…,m，执行以下步骤：(1) Alice秘密选取一个随机数k，1≤k≤p.(2) Alice将(H1,…,Hp)传递给Bob，其中Hk=Vj，其余都是随机生成.因为k是只有Alice知道的秘密数，所以Bob并不会知道Vj的位置.(3) Bob计算Zj,i=Hi·Y+rj,i=1,…,p.(4) Alice利用不经意传输协议得到Zj=Zj,k=Vj·Y+rj，而Bob并不知道k的值.5) Alice计算Zj=X·Y+v.此协议的通信代价为p·m·n·d，这里d表示为每个数据的二进制位数，p、m为安全参数，计算代价为m次协议.若已知直线L1：a1x+b1y=c1和直线外一个点P1(x1,y1)，则求出点P1(x1,y1)关于此直线的对称点).对称点的坐标计算公式为已知点P1(x1,y1)、P2(x2,y2)，以及一条直线L：ax+by=c，在直线L上找出一个点m，使得的值最小，最后求出此最小值.直线上有一个动点，要求出动点与两定点间距离的最小值，可以利用对称性来解决.根据定理：平面内两点间直线段最短，就可以求出距离的最小值.本题求的是两条线段长度之和的最小值.当两个定点在直线的不同侧时，最小值就是两个定点之间的距离.当两个定点在直线的同侧时，则以直线为对称轴，作其中一个点的对称点，最小值则为另一个点与此对称点间的距离[5].如图1所示.我们在此假设两个点在直线的同侧.输入：Alice拥有点P1(x1,y1)、P2(x2,y2)，Bob拥有一条直线L：ax+by=c.输出|+|mp2|的最小值.(m是直线L上的一个动点)执行过程：1) Alice在本地独立生成一个向量X=(x2，x1，y1，1)，Bob同样也在本地生成一个向量和Bob通过共同利用共享点积协议得到获得u1的值，Bob获得u2的值.2) Alice在本地独立生成一个向量M=(y2，y1，x1，1)，Bob也在本地独立生成一个向量和Bob通过共同利用共享点积协议得到获得v1的值，Bob获得v2的值.3) Alice 将得到的u1、v1的值传给Bob，Bob 将得到的u2、v2的值传给Alice.接着Alice和Bob各自在本地利用得到的数据计算出的值.协议结束.1) 正确性分析. 要计算出最小值，必须先求出其中一个点关于直线L的对称点.因此，我们先计算出点P1(x1,y1)关于直线L的对称点).最小值d即为点P1(x1,y1)与点)之间的距离.根据距离公式可以得到通过以上的分析，可以得知该协议是正确的.2) 安全性分析.协议在步骤(1)(2)(3)中均有信息交互，所以分别对这三步进行安全性分析.步骤(1)中，Alice、Bob只调用了点积协议，Alice得到了u1，Bob得到了u2，基于点积协议的安全性，Alice不能从u1推导出Y，Bob也不能从u2推导出X.步骤(2)与步骤(1)同样分析.步骤(3)中，Alice、Bob均得到u1、u2、v1、v2.Alice通过所得到的这4个值，可以分析得出下面的2个方程.但是总共有a、b、c3个未知数.所以方程组有无穷多解.因此，Alice无法推出Bob 的私有信息.同理，Bob也无法推出Alice的私有信息.综上所述，参与者Alice和Bob的私有信息均不会泄露，协议是安全的.3) 复杂性分析.本协议中调用了2次的点积协议.根据协议内容以及基于不经意传输协议(OT)的点积协议的复杂性可知，本协议的通信复杂度为2·p·m·n·d+2，计算复杂度为O(2mp).保护私有信息的计算几何(PPCG)问题在对私有信息高度敏感的领域有着重要的应用前景.本文通过利用点积协议，设计出了利用对称性保密求一条直线上的动点与两定点之间的最小值问题，并分析了该协议的正确性、安全性和复杂性.[1] 刘文,罗守山,陈萍. 保护私有信息的点线关系判定协议及其应用[J]. 北京邮电大学学报, 2008,31(2)：72-75.[2] Atallah M J, Du W.Secure multi-party computationalgeometry[C]//Lecture Notes in Computer Science 2125. Berlin:Springer ,2001:165-179.[3] 邱卫东，黄征，李祥学，等. 密码协议基础[M].北京：高等教育出版社，2009:120-121.[4] Mikhail J Atallah, Wenliang Du. Secure multi-party computational geometry[C]//In 7th Int. Workshop on Algorithms and DataStructures(WAD-S 2001), Lecture Note in Computer Sciences 2125, Springer-Verlag, New York:Springer-verlag,2001:165-179.[5] 王珽，罗文俊. 基于阈值的点线距离与位置关系保密判定协议[J]．计算机工程与应用，2010,46(13)：87-89.Key words: secure multi-party； computational geometry； scalar product protocol； the minimum value。

CGAL–THE COMPUTATIONAL GEOMETRYALGORITHM LIBRARYAndreas FabriINRIA2004,Route des Lucioles06903Sophia-Antipolis,FranceAndreas.Fabri@sophia.inria.frABSTRACTThe Cgal project()is a collaborative effort of several research institutes in Europe.The mission of the project is to make the most important of the solutions and methods developed in computational geometry available to users in industry and academia.Keywords:Computational geometry,C++,generic programming,exact computation paradigmINTRODUCTION Computational geometry is a research area in data structures and algorithm design which is a branch of theoretical computer science.In the seventies the term was coined,Preparata/Shamos wrote thefirst text book[20],the eighties brought theoretically op-timal,but unimplementable algorithms,the nineties saw a renaissance of simple algorithms,partially due to new complexitiy analysis methods1.The Cgal project was started in1995,by a group of European research institutes.The goal was to develop a computational geometry library,that is a homoge-neous and coherent collection of algorithms.The de-sign goals were robustness,efficiency,andflexibility. We content ourselves with an extended abstract be-cause several overview papers,library design papers, as well as papers about individual modules were pub-lished in the past.Instead we take excerpts from some of these publications and refer to further readings.1Obviously,this short“history of computational geom-etry”is an oversimplification.1.THE LIBRARYThe“product”of the Cgal project is Cgal,the Computational Geometry Algorithm Library,a highly modular C++library of data structures and algo-rithms.The data structures and algorithms were developed in academia,that is they are state of the art.The imple-mentations are not only academic proofs of concept, but they are robust,that is they can deal with degen-erate input,and they are time and space efficient. The library contains1000classes,300kloc,docu-mented on1000manual pages,that is it contains a critical mass of algorithms to be useful,and it is de-composed in reasonably sized classes that are well doc-umented.Cgal is currently supported on(although not technically limited to)Solaris,Linux,Irix,and Windows,in combination with the appropriate C++ compiler from Microsoft,Borland,Sgi,Kai and Gnu. We currently have release cycles of about9months, and about1500downloads per release.The library consists of a kernel,the basic library,a col-lection of algorithms and data structures,and a sup-port library.1.1KernelThe geometric kernel contains simple(constant-size) geometric objects like points,lines,segments,trian-gles,tetrahedra.There are geometric predicates on those objects.Furthermore,there are operations such as computing intersection and distance of objects and affine transformations.In fact Cgal offers several kernels.They differ in the representation of coordinates(Cartesian and homoge-neous coordinates),in the memory management(refer-ence counted or copying).There are even kernels that allow to execute two other kernels in parallel,and to check whether the geometric predicates give the same result.This is particularly useful tofind out where an algorithm that usesfloating point arithmetic has nu-merical problems,by executing it in parallel with an exact arithmetic.1.2Basic LibraryThe basic library contains more complex geometric objects and data structures:2D/3D convex hulls, 2D/3D triangulations,boolean operations on poly-gons,polygon decomposition in monotone or convex parts,a generic half-edge data structure,geometric optimisation algorithms based on a quadratic solver for computing minimum enclosing sphere or ellipses in arbitrary dimension,arrangements of curves in the plane,multidimensional search structures for window queries,etc.The basic library is independent from the kernel.Ev-ery algorithm defines in a very precise way which prim-itives it uses.For example,a2D convex hull algorithm can take points as input and must be able to decide if one point lies to the left of another point,and to decide when you go from one point via a second point to a third point,if you make a left or a right turn.In this case the algorithm is parameterized by the point type and the two predicates that work on the point type.The algorithm is implemented in terms of the types and operations of the interface only.Generally, the Cgal kernel provides these types and predicates. For ease of use the algorithm has default arguments for these parameters,that is the user has not to worry about this,but has means of changing it,if necessary. Among the data structures of the library,triangula-tions are probably the most relevant ones for mesh gen-eration.All triangulation data structures have pow-erful Api s,and they are fully dynamic,that is they offer methods to insert and to remove points and con-straints.Cgal offers a Delaunay and a regular Delaunay trian-gulation.In2D it offers additionally constrained and constrained Delaunay triangulation.A Delaunay triangulation of a set of points fulfills the following empty circle property:the circumscribing circle of any facet of the triangulation contains no data point in its interior.For a point set with no subset of four cocircular points the Delaunay triangulation is unique,it is the dual of the Voronoi diagram of the points.A constrained triangulation is a triangulation of a set of points that has to include among its edges a given set of segments joining the points.The corresponding edges are called constrained edges.A constrained Delaunay triangulation is a triangula-tion with constrained edges which tries to be as much Delaunay as possible.As constrained edges are not necessarily Delaunay edges,the triangles of a con-strained Delaunay triangulation do not necessarily ful-fill the empty circle property but they fulfill a weaker constrained empty circle property.To state this prop-erty,it is convenient to think of constrained edges as blocking the view.Then,a triangulation is con-strained Delaunay,iffthe circumscribing circle of any facets encloses no vertex visible from the interior of the facet.Cgal has a triangulation class that efficiently answers point location queries.Internally,the data structure is a hierarchy of triangulations.The triangulation at the lowest level is the original triangulation where opera-tions and point location are to be performed.Then at each succedding level,the data structure stores a triangulation of a small random sample of the vertices of the triangulation at the preceeding level.Point lo-cation is done through a top down nearest neighbor query.The nearest neighbor query isfirst performed naively in the top level triangulation.Then,at each following level,the nearest neighbor at that level is found through a linear walk performed from the near-est neighbor found at the preceeding level.Because the number of vertices in each triangulation is only a small fraction of the number of vertices of the preceed-ing triangulation,the data structure remains small and achieves fast point location queries on real data.This structure has an optimal behaviour when it is built for 2D/3D Delaunay triangulations[7].Because in prac-tice it also works well for other types of triangulations, it is parameterized with a triangulation class.Efficiency is a must in order to be of practical rele-vance.For example the construction of a3D Delau-nay triangulation of2million points in a surface re-construction application takes340sec and650MB of memory,on a Pentium III at550MHz.We currently work on constrained3D as well as on conformal Delaunay triangulation.The latter means that Steiner points are added,so that the Delaunay triangulation of the points automatically respects the constraints.1.3Support LibraryThe support library contains non-geometric data structures,and interfaces to other libraries providing visualization and numberetypes.2.TECHNOLOGYThe Cgal library represents cutting edge technology. This holds for the geometric algorithms,as well as for the software design,where we did not reinvent the wheel,but followed best practice.2.1C++Cgal is implemented in C++[15].There were sim-ilar efforts for making geometry libraries:the Xyz Geobench[21]was written in Pascal and the Geome-try Workbench[17]was written in Smalltalk.Because these language disappeared or were never widely ac-cepted these efforts were deemed to fail.Being as mainstream as possible was not the only rea-son for choosing C++.It is object-oriented,that is it allows a clean separation of specification and imple-mentation.It supports polymorphism,and most im-portantly for Cgal,it supports the generic program-ming paradigm.2.2Generic ProgrammingGeneric programming[18]gives a tremendousflexi-bility during development,and efficient code at run time of a program.Its power became apparent with the Stl,the Standard Template Library,which is now part of the Iso C++standard,and shipped with every C++compiler.As the Stl,Cgal makes use of the concept of iterators to decouple data structures from algorithms operating on them.Iterators are an abstraction of pointers,that is everything that implements a dereference and incre-ment operator is an iterator2For example,a set of points can be inserted into a triangulation with a function that has the same sig-nature independently from the implementation of the set.This avoids copying to one canonical container, or an inflation of functions with“the most common containers”as argument.typedef Cartesian<double>K;typedef K::Point_2Point;typedef Istream_iterator<Point,istream>Iter; Triangulation_2<K>T;vector<Point>v;//points taken from a vector of pointsT.insert(v.begin(),v.end());//points taken from standard inputT.insert(Iter(cin),Iter());Because a triangulation is a container of vertices and faces,it provides iterators that allow to enumerate them.class Delaunay_triangulation_2{Face_iterator faces_begin();Face_iterator faces_end();};Because the faces adjacent to a vertex are in a cir-cular order with no natural beginning or end,Cgal introduces the concept of circulators.class Delaunay_triangulation_2::Vertex{Face_circulator incident_faces();};Similar to Stl containers being parameterized with the type of objects they contain,the geometric ker-nels provided by Cgal are parameterised with a num-ber type,e.g.,floating point,rational,or real exact numbers.This offers a trade-offbetween robustness and efficiency.Best results are obtained by combining them,what we will explain in the next section.2A simplification again.In fact there is a complete hi-erarchy of iterators with different requirements on the set of operations.Cartesian<double>//floating point Homogeneous<Gmpz>//rationalsCartesian<leda_real>//real numbers Cartesian<Filtered_exact<double,leda_real>>This parameterization is only the tip of the iceberg concerning the adaptability and extensibility of the kernel[13].As stated earlier the basic library is independent from the kernel.All data structures in the basic library are parameterised with a class that provides all the geometric primitives the data structure uses. template<class Geometry>class Delaunay_triangulation_2{void insert(Geometry::Point_2t){if(Geometry::orientation(p,q,t)==..)if(Geometry::incircle(p,q,r,t))}};For most data structures any Cgal kernel can be cho-sen as template argument.Exceptions are data struc-tures that need very particular predicates,which are not expected to be useful in other contexts.This mechanism further allows to use projection classes.For example,3D points,together with pred-icates that compute on the projection of the points, without explicitely constructing2D points.This al-lows to triangulate the points of a Gis terrain model, or the face of a polyhedron,without changing a line of code in the triangulation data structure.Finally,this allows to seamlessly integrate a Cgal tri-angulation in an already existing application,and to let it operate on the application point type.In fact,the triangulation classes have a second tem-plate argument besides the geometry,namely the com-binatorics.Triangulations can be represented by ver-tices and faces,where each face has a pointer to its three incident faces and three incident vertices,and where each vertex has a pointer to an incident face. Alternatively,it can be represented by vertices and halfedges,where each halfedge knows its successor,its reverse halfedge,and a vertex,and where each vertex knows an incident halfedge.Although a face based representation is more compact,it may be interesting for an application to use the halfedge data structure, as the triangulation may be a single step in an ap-plication pipeline,or in an application loop,so that converting forth and back between different represen-tations is no option.Stroustrup[26]provides a general introduction to C++ template programming.Austern[1]provides a good reference for generic programming and the Stl,and a good reference for the C++Standard Library is the book of Josuttis[14].Cgal is not the only library which has adopted this paradigm.It is used by the Matrix Template Library [22],by the Boost Graph Library[23],by the Grid Algorithm Library[3],in the oonumerics[19],and the Blitz++project[27].Note that it is an explicit goal of the two scientific computing projects to offer solutions that are as fast as Fortran code.They know that their community cannot make any compromise on speed for only getting aesthetically or software engineering wise better code.2.3Exact ComputingThe established approach for robust geometric al-gorithms following the exact computation paradigm [28]requires the exact evaluation of geometric predi-cates,i.e.,decisions derived from geometric computa-tions have to be correct.While this can be achieved straightforwardly by relying on an exact number type, this is not the most efficient approach,and the idea of so-calledfilters has been developed to speed up the exact evaluation of predicates[4,11,24].The basic idea is to use afiltering step before the costly computation with an exact number type.Thefilter step evaluates quickly and approximately the result of the predicate,but is also able to decide if the answer it gives is certified to be true or if there is a risk for a false answer,in which case the exact number type is used tofind the correct answer.Cgal implements such afiltering technic using inter-val arithmetic,via the Interval nt number type[4]. This number type stores an interval of values which bounds are double s,and propagates the round-offer-rors that occur duringfloating point computations. The comparison operators on this number type have the property that they throw a C++exception in the case that the two intervals to be compared overlap. When this occurs,it means that thefilter can not cer-tify the exactness of the result using its approximate computation.Then we have tofind a different method to evaluate exactly the predicate,by using an exact but slower number type.As this failure is supposed to happen rarely on average,the overall performance of the algorithm is about the same as the evaluation of the predicate over the intervals,which is pretty fast.Note that Cgal offers only few exact number types. We concentrate on our core competence,namely ge-ometric algorithms,including geometric predicates. The generic programming approach allows to plug in arbitrary precision number types for integers and ra-tionals(Gmp[12]),and approximations of reals(Core [16],and Leda[5]).3.APPLICATION AREASCgal is enabling technology,that is it does not pro-vide a vertical solution in one application area,but provides geometric primitives for many very different application areas.Here are some examples for how Cgal data structures get used:3D regular triangulation for transition mesh generation in geological modelling[2],3D Delaunay triangulation for coarse grained molecular dynamics [10],and for surface reconstruction[8],2D Delaunay triangulations for cell decomposition in air traffic con-trol,polyhedral surfaces for surface extraction from Mri s,smallest enclosing spheres for fast collision de-tection in games,boolean operations on polygons for segmentation algorithms in imaging,arrangements of arcs of circles and polylines for controlling processing tools as laser and mill.4.CONCLUSION AND OUTLOOKIn itsfirst years the Cgal project was seen scepti-cally as we used very advanced C++techniques,that nowadays are widely accepted as best practice,and supported by almost all C++compilers.A more philosophically discussion,entitled“gems vs. libraries”,is about whether libraries force to make compromises leading to inefficiencies.Our experience is that only the design process is slower,as everything has tofit in the big picture.On the other hand it is often obvious how something has to be done,if one is familiar with the overall design ideas of the library. Also,by many the library is perceived as monolithic. However,this is not a technical,but a packaging and documentation problem,which we plan to overcome. Cgal is used in teaching,in computational geome-try research and by people that have a clear end-user perspective as they work outside of computational ge-ometry and computer science.Although Cgal is distributed as source code,it is not open source,which is currently under discussion.It makes sense to do it now,because the design of the library is stable,we start having a critical mass of algorithms and data structures to further build on, and the next step is broadening the base,a task that needs a community effort.So far we have not reached the goal to be widely used by industry.This is partially due to the fact that no company offers support for it,something that is about to change as we work towards a Cgal company.ACKNOWLEDGMENTSThis work has been supported by Esprit Ltr projects No.21957(Cgal)and No.28155(Galia).Thanks to all those colleagues from the Cgal project from whom I scavenged a paragraph or code sniplet.REFERENCES[1]M.H.Austern Generic Programming and theSTL.Addison-Wesley,1998.[2]S.Balaven,C.Bennis,J-D.Boissonnat&S.Sarda.Generation of hybrid grids using power diagrams.In Proc.Numerical Grid Gen-eration in Field Simulations,2000.[3]G.Berti A Generic Toolbox for the Grid Crafts-man.17th GAMM-Seminar Leipzig on“Con-struction of Grid Generation Algorithms”,2001.[4]H.Br¨o nnimann,C.Burnikel&S.Pion.In-terval arithmetic yields efficient dynamicfilters for computational geometry.Proc.14th Annu.ACM put.Geom.(1998),pp.165–174.[5] C.Burnikel,K.Mehlhorn&S.SchirraThe LEDA class real number.Technical Re-port MPI-I-96-1-001,Max-Planck Institut In-form.,Saarbr¨u cken,Germany,Jan.1996.[6]CGAL,the Computational Geometry Algo-rithms Library./.[7]O.Devillers Improved incremental random-ized Delaunay triangulation.In Proc.14th Annu.ACM put.Geom.,pages106-115, 1998.[8]T.K.Dey,J.Giesen&J.Hudson.Delau-nay based shape reconstruction from large data.Proc.IEEE Symposium in Parallel and Large Data Visualization and Graphics,2001.[9] A.Fabri,G.-J.Giezeman,L.Kettner,S.Schirra&S.Sch¨o nherr On the design of Cgal,the computational geometry algorithms li-brary,Software-Practice and Experience,2000, Vol.30,1167-1202.[10]G.De Fabritiis,P.V.Coveney&E.G.Flekkoy Multiscale modelling of complexfluids,Proceedings of5th European SGI/Cray MPP Workshop,Bologna(Italy)(1999)[11]S.Fortune&C.J.Van Wyk.Static analysisyields efficient exact integer arithmetic for com-putational geometry.ACM Trans.Graph.15,3 (July1996),223–248.[12]Gmp–Arithmetic without limitations./gmp/[13]S.Hert,M.Hoffmann,L.Kettner,S.Pion&M.Seel An Adaptable and Extensible Geom-etry Kernel.5th Workshop on Algorithm Engi-neering,BRICS,University of Aarhus,Denmark, August28-30,2001.[14]N.M.Josuttis The C++Standard Library,ATutorial and Reference.Addison-Wesley,1999.[15]International standard ISO/IEC14882:Pro-gramming languages–C++.American National Standards Institute,11West42nd Street,New York10036,1998.[16]V.Karamcheti,C.Li,I.Pechtchanski&C.Yap.The CORE Library Project,1.2ed.,1999./exact/core/.[17] A.Knight,J.May,J.McAffer,T.Nguyen&J.-R.Sack A Computational Geometry Workbench.ACM Symposium on Comutational Geometry,1990.[18] D.R.Musser&A.A.Stepanov Generic pro-gramming.In1st Intl.Joint Conf.of ISSAC-88 and AAEC-6(1989),Springer LNCS358,pp.13–25.[19]Scientific Computing in Object-Oriented Lan-guages[20] F.Preparata,M.I.Shamos ComputationalGeometry–An Introduction.Springer Verlag, New York,1985.[21]P.Schorn The XYZ GeoBench for the ex-perimental evaluation of geometric algorithms, Series in Discrete Mathematics and Theoretical Computer Science,Volume15,137-151,1994. [22]J.G.Siek& A.Lumsdaine The MatrixTemplate Library:Generic Components for High perfromance scientific puting in Science and Engineering,1999./research/mtl/[23]J.G.Siek,A.Lumsdaine&L.-Q.Lee TheBoost Graph Library./libs/libraries.htm[24]Shewchuk,J.R.Adaptive precisionfloating-point arithmetic and fast robust geometric pred-icates.Discrete Comput.Geom.18,3(1997), 305–363.[25]Standard Template Library programmer’sguide./tech/stl/.[26] B.Stroustrup The C++Programming Lan-guage,3rd Edition.Addison-Wesley,1997. [27]T.Veldhuizen Techniques for scientific C++.Technical Report542,Department of Computer Science,Indiana University,2000./~tveldhui/papers/techniques/.[28] C.K.Yap&T.Dub´e The exact computationparadigm.In Computing in Euclidean Geometry,D.-Z.Du and F.K.Hwang,Eds.,2nd ed.,vol.4of Lecture Notes Series on Computing.World Sci-entific,Singapore,1995,pp.452–492.。

国外数学期刊英汉对照作者:admin 日期:2009-06-17字体大小: 小中大Advances in Applied Mathematics 应用数学Advances in Applied Probability 应用概率论进展Advances in Computational Mathematics 计算数学进展Advances in Mathematics 数学进展Algebra Colloquium 代数学讨论会Algebras and Representation Theory 代数和表示理论American Mathem atical Monthly 美国数学月刊American Statistician 美国统计员Annals of Applied Probability 应用概率论年报Annals of Global Analysis and Geometry 整体分析与几何学年报Annals of Mathematics and Artificial Intelligence 人工智能论题年报Annals of Operations Research 运筹学研究年报Annals of Probability 概率论年报Annals of Pure and Applied Logic 抽象和应用逻辑年报Annals of Statistics 统计学年报Annals of The Institute of Statistical Mathematics 统计数学学会年报Applicable Algebra in Engineering Communication and Computing 代数在工程通信与计算中的应用Applied and Computational Harmonic Analysis 调和分析应用和计算Applied Categorical Structures 应用范畴结构Applied Mathematics and Computation 应用数学与计算Applied Mathematics and Optimization 应用数学与最优化Applied Mathematics Letters 应用数学快报Archive for History of Exact Sciences 科学史档案Archive for Mathem atical Logic 数理逻辑档案Archive for Rational Mechanics and Analysis 理性力学和分析档案Archives of Computational Methods in Engineering 工程计算方法档案Asymptotic Analysis 渐近线分析Autonomous Robots 机器人British Journal of Mathematical & Statistical Psychology 英国数学与统计心理学杂志Bulletin of The American Mathematical Society 美国数学会快报Bulletin of the London Mathematical Society 伦敦数学会快报Calculus of Variations and Partial Differential Equations 变分法与偏微分方程Combinatorics Probability & Computing 组合概率与计算Combustion Theory and Modeling 燃烧理论建模Communications in Algebra 代数通讯Communications in Contemporary Mathematics 当代数学通讯Communications in Mathematical Physics 数学物理学通讯Communications in Partial Differential Equations 偏微分方程通讯Communications in Statistics-Simulation and Computation 统计通讯–模拟与计算Communications on Pure and Applied Mathematics 纯数学与应用数学通讯Computational Geometry-Theory and Applications 计算几何- 理论与应用Computational Optimization and Applications 优化计算与应用Computational Statistics & Data Analysis 统计计算与数据分析Computer Aided Geometric Design 计算机辅助几何设计Computer Physics Communications 计算机物理通讯Computers & Mathematics with Applications 计算机与数学应用Computers & Operations Research 计算机与运筹学研究Concurrent Engineering-Research and Applications 共点工程- 研究与应用Conformal Geometry and Dynamics 投影几何与力学Decision Support Systems 决策支持系统Designs Codes and Cryptography 编码设计与密码系统Differential Geom etry and Its Applications 微分几何及其应用Discrete and Continuous Dynamical Systems 离散与连续动力系统Discrete Applied Mathematics 应用离散数学Discrete Computational Geometry 离散计算几何学Discrete Event Dynamic Systems-Theory and Applications 离散事件动态系统- 理论和应用Discrete Mathematics 离散数学Educational and Psychological Measurement 教育与心理测量方法Engineering Analysis with Boundary Elem ents 工程边界元素分析Ergodic Theory and Dynamical System s 遍历理论和动力系统European Journal of Applied Mathematics 欧洲应用数学杂志European Journal of Combinatorics 欧洲组合数学杂志European Journal of Operational Research 欧洲运筹学杂志Experimental Mathematics 实验数学Expert Systems with Applications 专家系统应用Finite Fields and Their Applications 有限域及其应用Foundations of Computational Mathematics 计算数学基础Fuzzy Sets and Systems 模糊集与模糊系统Glasgow Mathematical Journal 英国格拉斯哥数学杂志Graphs and Combinatorics 图论与组合数学IEEE Robotics & Automation Magazine IEEE机器人与自动化杂志IEEE Transactions on Robotics and Automation IEEE机器人与自动化学报IMA Journal of Applied Mathem atics IMA应用数学学报IMA Journal of Mathem atics Applied in Medicine and Biology IMA数学在医药与生物中的应用杂志IMA Journal of Numerical Analysis IMA数值分析学报Information and Computation 信息与计算Insurance Mathematics & Economics 保险数学和经济学International Journal for Numerical Methods in Engineering 国际工程数值方法杂志International Journal of Algebra and Computation 国际代数和计算杂志International Journal of Computational Geometry & Applications 国际计算几何应用杂志International Journal of Computer Integrated Manufacturing 国际计算机集成制造业国际杂志International Journal of Game Theory 国际对策论国际杂志International Journal of Mathematics 国际数学杂志International Journal of Production Research 国际研究成果杂志International Journal of Robotics Research 国际机器人研究杂志International Journal of Systems Science 国际系统科学杂志International Statistical Review 国际统计评论Inverse Problems 反比问题Journal of Algebra 代数学报Journal of Algebraic Combinatorics 代数组合数学学报Journal of Algebraic Geometry 代数几何学报Journal of Algorithm s 算法学报Journal of Applied Mathematics and Mechanics 数学应用与力学学报Journal of Applied Probability 应用概率杂志Journal of Approximation Theory 近似值理论杂志Journal of Combinatorial Optimization 组合最优化学报Journal of Combinatorial Theory Series B 组合理论学报B辑Journal of Combinatorial Theory Series A 组合理论学报A辑Journal of Computational Acoustics 声学计算杂志Journal of Computational Analysis and Applications 计算分析与应用学报Journal of Computational and Applied Mathematics 计算与应用数学杂志Journal of Computational Biology 生物计算杂志Journal of Computational Mathematics 计算数学学报Journal of Computational Neuroscience 神经系统计算杂志Journal of Computational Neuroscience 神经系统计算杂志Journal of Differential Equations 微分方程组学报Journal of Econom etrics 计量经济学会会刊Journal of Engineering Mathematics 工程数学学报Journal of Functional Analysis 泛函分析学报Journal of Geometry and Physics 几何学和物理学学报Journal of Global Optimization 整体优化学报Journal of Graph Theory 图论理论学报Journal of Group Theory 群论理论学报Journal of Lie Theory 展开理论杂志Journal of Mathematical Analysis and Applications 数学分析和应用学报Journal of Mathematical Biology 数学生物学杂志Journal of Mathematical Economics 数学经济学学报Journal of Mathematical Imaging and Vision 成像和视觉数学学报Journal of Mathematical Physics 数学物理学的杂志Journal of Mathematical Psychology 数学心理学杂志Journal of Multivariate Analysis 多变量分析杂志Journal of Nonlinear Science 非线性数学学报Journal of Number Theory 数论学报Journal of Operations Management 操作管理杂志Journal of Pure and Applied Algebra 纯代数与应用代数学学报Journal of Statistical Planning and Inference 统计规划和推论杂志Journal of Symbolic Computation 符号计算学报Journal of the American Mathematical Society 美国数学会杂志Journal of the London Mathematical Society-Second Series 伦敦数学会杂志- 第二辑Journal of the Royal Statistical Society Series B-Statistical Methodology 皇家学会系列杂志B 辑-统计方法学Journal of The Royal Statistical Society Series C-Applied Statistics 皇家学会系列杂志C - 应用统计Journal of Theoretical Probability 概率理论杂志K-Theory K-理论Lecture Notes in Economics and Mathematical Systems 经济学和数学体系讲座Lecture Notes on Mathematics 数学讲座Letters in Mathematical Physics 数学物理学通讯Linear Algebra and Its Applications 线性代数及其应用Mathematical Biosciences 数理生物学Mathematical Finance 数理财金学Mathematical Geology 数理地质学Mathematical Intelligencer 数学情报Mathematical Logic Quarterly 数理逻辑学报Mathematical Methods in the Applied Sciences 数学应用学科Mathematical Methods of Operations Research 运筹学研究Mathematical Models & Methods in Applied Sciences 数学模拟与应用方法Mathematical Physics Electronic J 数学物理电子杂志Mathematical Proceedings of the Society 数学学会学报Mathematical Programming 数学规划Mathematical Social Sciences 数学社会科学Mathematics and Computers in Simulation 数学与电脑模拟Mathematics and Mechanics of Solids 数学与固体力学Mathematics Archives 数学档案库Mathematics Magazine 数学杂志Mathematics of Computation 计算数学Mathematics of Control Signals and Systems 控制信号系统数学Memoirs of the American Mathematical Society 美国数学会备忘录Modem Logic 现代逻辑学Nonlinear Analysis-Theory Methods & Applications 非线性分析- 理论与应用Nonlinearity 非线性特性Notices 短评Numerical Algorithms 数字算法Numerical Methods for Partial Differential Equations 偏微分方程式数值方法Oxford Bulletin of Economics and Statistics 牛津大学经济与统计快报Potential Analysis 位势分析Proceedings of the American Mathem atical Society 美国数学会会议录Proceedings of the London Mathematical Society 伦敦数学会会议录Proceedings of the Royal Society of Edinburgh Section A-Mathem atics 英国爱丁堡皇家学会会议录A分册数学Quarterly Journal of Mathematics 数学季刊Quarterly Journal of Mechanics and Applied Mathematics 数学与应用数学季刊Quarterly of Applied Mathematics 应用数学季刊Queueing Systems 排列系统Random Structures and Algorithms 随机结构与算法Reports on Mathematical Physics 数学物理学报告Representation Theory 表示法理论Robotics and Autonomous Systems 机器人技术和自动系统Rocky Mountain Journal of Mathematics 数学难题学报Set-Valued Analysis 精点分析Statistical Papers 统计学论文Statistics & Probability Letters 统计和概率通讯Statistics and Computing 统计和计算Stochastic Analysis and Applications 随机分析和应用Stochastic Environm ental Research and Risk Assessm ent 随机环境论研究和风险评估Stochastic Processes and Their Applications 随机过程及其应用Studies in Applied Mathematics 应用数学研究The College Mathematics Journal 大学数学杂志The Electronic Journal of Combinatorics 组合数学电子期刊Theory of Computing Systems 计算方法理论Theory of Probability and Its Applications 概率理论及其应用程序理论Topology 拓扑学Topology and Its Applications 拓扑学及其应用Transactions of the American Mathematical Society 美国数学会学报Applied Numerical Mathematics《应用数值数学》荷兰Annales Scientifiques de l'École Normale Supérieure《高等师范学校科学纪事》法国Applied and Computational Harmonic Analysis《应用和计算谐波分析》美国Applied Stochastic Models in Business and Industry《商业与工业应用随机模型》英国Acta Applicandae Mathematicae 《应用数学学报》荷兰Advances in Computational Mathematics《计算数学进展》荷兰Annals of Mathematics and Artificial Intelligence《数学与人工智能纪事》荷兰Annals of Operations Research《运筹学纪事》荷兰Annals of the Institute of Statistical Mathematics《统计数理研究所纪事》日本。