CGAL 3.1 differs from CGAL 3.0 in the platforms that are supported and in functionality. There have also been a number of bug fixes for this release.
Changelog
Supported platforms
Additional supported platforms:
 MS Visual C++, version 7.3. and 8.0
 Intel 8.0
 SunPro CC versions 5.4 and 5.5 on Solaris
 GNU g++ versions 3.4 on Linux, Solaris, Irix, cygwin, FreeBSD, and MacOS X
 Darwin (MacOS X) and IA64/Linux support.
No longer supported
 MS Visual C++, version 7.0
General
 The CORE 1.7 library for exact real arithmetic.
 Updated GMP to 4.1.3.
 Added Mpfr a library for multipleprecision floatingpoint computations with exact rounding.
 Added Boost 1.32.0 (only include files).
Installation
 new option
disableshared
to omit building libCGAL.so.
Manuals
 Merged all major manuals in one multipart manual, which provides now crosslinks between the CGAL Kernel, the CGAL Basic Library, and the CGAL Support Library HTML manuals.
 Improved layout.
Kernels
 Improved efficiency of filtered kernels.
 More predicates and constructions.
2D Segment Voronoi Diagram (new package)
 A data structure for Voronoi diagrams of segments in the plane under the Euclidean metric. The Voronoi edges are arcs of straight lines and parabolas. The algorithm provided in this package is incremental.
2D Conforming Triangulations and Meshes (new package)
 An implementation of Shewchuk’s algorithm to construct conforming triangulations and 2D meshes.
3D Boolean Operations on Nef Polyhedra (new package)
 A new class (Nef_polyhedron_3) representing 3D Nef polyhedra, a boundary representation for cellcomplexes bounded by halfspaces that supports boolean operations and topological operations in full generality including unbounded cells, mixed dimensional cells (e.g., isolated vertices and antennas). Nef polyhedra distinguish between open and closed sets and can represent nonmanifold geometry.
2D and Surface Function Interpolation (new package)
 This package implements different methods for scattered data interpolation: Given measures of a function on a set of discrete data points, the task is to interpolate this function on an arbitrary query point. The package further offers functions for natural neighbor interpolation.
Planar Nef polyhedra embedded on the sphere (new package)
 A new class (Nef_polyhedron_S2) designed and supported mainly to represent sphere neighborhoods around vertices of the three dimensional Nef polyhedra.
Box_intersection_d (new package)
 A new efficient algorithm for finding all intersecting pairs for large numbers of isooriented boxes, i.e., typically these will be bounding boxes of more complicated geometries. Useful for (self) intersection tests of surfaces etc.
2D Snap Rounding (new package)
 Snap Rounding is a well known method for converting arbitraryprecision arrangements of segments into a fixedprecision representation. In the study of robust geometric computing, it can be classified as a finite precision approximation technique. Iterated Snap Roundingis a modification of Snap Rounding in which each vertex is at least halfthewidthofapixel away from any nonincident edge. This package supports both methods.
Triangulation_3
 Triangulation_3: added
operator==()
, removedpush_back()
andcopy_triangulation()
.  Delaunay_3 : added
nearest_vertex()
,move_point()
,vertices_in_conflict()
.  Regular_3 : added filtered traits class, and
nearest_power_vertex()
.
Planar_map and Arrangement_2
 The interface of the two traits functions that compute the
intersection of two given curves changed. The functions
nearest_intersection_to_right()
andnearest_intersection_to_left()
return an object of typeCGAL::Object
that represents either an empty intersection, a point, or an overlapping subcurve.  Requirements to define two binary tags were added to the traits
concept of the Planar_map as follows:

Has_left_category*
 indicates whether the functionscurves_compare_y_at_x_left()
and nearest_intersection_to_left() are implemented in the traits model. Has_reflect_category
 indicates whether the functionspoint_reflect_in_x_and_y()
andcurve_reflect_in_x_and_y()
are implemented in the traits model. They can be used as an alternative to the two function in the previous item.  A new constructor of the
Segment_cached_2
type that represents a segment in theArr_segment_cached_traits_2
traits class was introduced. The new constructor accepts the segment endpoints as well as the coefficients of the underlying line.  A new version of the conicarc traits, based on CORE version 1.7
was introduced. This new traits class makes use of CORE’s
rootOf()
operator to compute the intersection points in the arrangement, making its code much simpler and more elegant than the previous version. In addition, new constructors for conic arcs are provided. The new traits class usually performs about 30% faster than the version included in CGAL 3.0  The traits class that handles continuous piecewise linear
curves, namely
Arr_polyline_traits_2
, was rewritten. The new class is parametrized with a traits class that handles segments, say Segment_traits. The polyline curve defined within theArr_polyline_traits_2
class is implemented as a vector of segments of typeSegment_traits::Curve_2
.  A meta traits class, namely
Arr_curve_data_traits_2
, that extends the curve type of the planarmap with arbitrary additional data was introduced. It should be instantiated with a regular traitsclass and a class that contains all extraneous data associated with a curve.  The class that represents the trapezoidaldecomposition point
location strategy was renamed to
Pm_trapezoid_ric_point_location
.  The Arrangement demo was rewritten. It covers many more features, has a much better graphical user interface, and comes with online documentation.
 Few bugs in the sweepline module related to overlapping vertical segments were fixed. This module is used by the aggregate insert method that inserts a collection of curves at once.
Triangulation_2
 Added a filtered trait class in the regular triangulation.
 Added split and join operations in the triangulation data structure class.
Alpha_shapes_3
 major changes in the implementation of the class
Alpha_shapes_3
.  New implementation results in a true “GENERAL” mode allowing null and negative alphavalues. It also fixed the edges classification bug and introduces a classification of vertices.
Min_ellipse_2
 made access to approximate double representation public
 fixed bugs in conversion to double representation
 added
is_circle()
method  minor performance improvements
Min_sphere_of_spheres_d:
 The models
Min_sphere_of_spheres_d_traits_2<K,FT,UseSqrt,Algorithm>
,Min_sphere_of_spheres_d_traits_3<K,FT,UseSqrt,Algorithm>
, andMin_sphere_of_spheres_d_traits_d<K,FT,Dim,UseSqrt,Algorithm>
of conceptMinSphereOfSpheresTraits
now represent a sphere as astd::pair<Point,Radius>
(and not any more as aCGAL::Weighted_point<Point,Weight>
)  Internal code cleanup; in particular, implementation details don’t pollute the namespace CGAL anymore
Polyhedron_3
 New Tutorial on CGAL Polyhedron for Subdivision Algorithms with interactive demo viewer in source code available.
 Added example program for efficient selfintersection test.  Added small helper functions, such as vertex_degree, facet_degree, edge_flip, and is_closed.
Apollonius Graph (Voronoi of Circles)
 Reduced memory requirements by approximately a factor of two.