CGAL 3.6 offers the following improvements and new functionality over CGAL 3.5.1:

## Changelog

### General

- Boost version 1.34.1 (or later) is now required.

### Arithmetic and Algebra

#### Algebraic Kernel (new package)

- This new package is targeted to provide black-box implementations of state-of-the-art algorithms to determine, compare and approximate real roots of univariate polynomials and bivariate polynomial systems. It includes models of the univariate algebraic kernel concept, based on the library RS.

#### Number Types

- Two new arbitrary fixed-precision floating-point number types have been added: the scalar type Gmpfr and the interval type Gmpfi, based on the MPFR and MPFI libraries respectively.

### Geometry Kernels

#### 2D and 3D Geometry Kernel

- Add new
`do_intersect()`

and`intersection()`

overloads:`do_intersect(Bbox_3, Bbox_3/Line_3/Ray_3/Segment_3)`

`intersection(Triangle_3, Line_3/Ray_3/Segment_3)`

### Polygons

#### 2D Regularized Boolean Set-Operations

- Fixed
`General_polygon_set_2::arrangement()`

to return the proper type of object.

### Arrangement

#### 2D Arrangements

- Fixed passing a (const) traits object to the constructor of
`Arrangement_2`

. - Introduced
`Arrangement_2::fictitious_face()`

, which returns the fictitious face in case of an unbounded arrangement. - Fixed a bug in Bezier-curve handling.
- Added (back) iterator,
`number_of_holes()`

,`holes_begin()`

, and`holes_end()`

to the default DCEL for backward compatibility. - Added (simple) versions of the free
`overlay()`

function. It employs the default overlay-traits, which practically does nothing.

### Polyhedron

- Fixed a compilation errors in
`demo/Polyhedron/`

:- issue with the location of
`qglobal.h`

of Qt4 on MacOS X, - missing
`texture.cpp`

, if TAUCS is used,

- issue with the location of
- Fixed the location of built plugins of demo/Polyhedron/, when CGAL is configured with WITH_demos=ON
- Fixed a bug in test_facet function of the incremental builder: the function did not test if while a new facet makes a vertex manifold, no other facet incident to that vertex breaks the manifold property.

### Triangulations and Delaunay Triangulations

#### 2D/3D Regular Triangulations

- Weighted_point now has a constructor from Cartesian coordinates.

#### 3D Triangulations

`Regular_triangulation_3`

: semi-static floating-point filters are now used in its predicates, which can speed up its construction by a factor of about 3 when`Exact_predicates_inexact_constructions_kernel`

is used.- The class
`Regular_triangulation_filtered_traits_3`

is deprecated, the class`Regular_triangulation_euclidean_traits_3`

must be used instead. The predicates of that traits will be filtered if the kernel given as template parameter of that traits is itself a filtered kernel. `Triangulation_hierarchy_3`

is now deprecated, and replaced by a simpler CGAL::Fast_location policy template parameter of`Delaunay_triangulation_3`

.- The old version of
`remove()`

(enabled with`CGAL_DELAUNAY_3_OLD_REMOVE`

) has been deleted.

#### 3D Periodic Triangulations

- New demo: 3D periodic Lloyd algorithm.
- New functionality for Voronoi diagrams: dual of an edge and of a vertex, volume and centroid of the dual of a vertex.
- The package can now be used with the 3D Alpha Shapes package to compute periodic alpha shapes.

#### 3D Alpha shapes

- The class
`Weighted_alpha_shape_euclidean_traits_3`

is deprecated, the class`Regular_triangulation_euclidean_traits_3`

must be used instead. - The package can now be used together with the 3D Periodic Triangulation package to compute periodic alpha shapes.

#### 2D/3D Triangulations, 2D Segment Delaunay Graph, 2D Apollonius Graph, and 3D Periodic Triangulations

- The constructor and insert function taking ranges now produce structures whose iterator orders is now deterministic (same at each run).

### Mesh Generation

#### 2D Mesh Generation

- The 2D mesh generator can now be used with a constrained Delaunay
triangulation with constraints hierarchy
(
`Constrained_triangulation_plus_2`

). - In some cases (refinement of a constrained edge that is on the convex hull), the 2D mesh generator from CGAL-3.4 and CGAL-3.5 could create invalid triangulations. This bug is now fixed.

#### 3D Mesh Generation

- The mesh generator has been enriched with an optimization phase to provide 3D meshes with well shaped tetrahedra (and in particular no slivers). The optimization phase involves four different optimization processes: two global optimization processes (ODT and Lloyd), a perturber and an exuder. Each of these processes can be activated or not, and tuned to the users needs and to available computer resources.

### Support library

#### CGAL ipelets

- Add support for version 7 of Ipe.