Cylindrical Algebraic Decomposition

A cylindrical algebraic decomposition of is a finite set partition of into cells, with a fixed ordering of the coordinates, such that the coordinate projections of any two cells onto the first coordinates are either identical or disjoint for each (Basu 2017). The cells are connected semialgebraic sets built recursively as follows.

A cell in is an open interval or a point. A cell in has one of the forms

(1)

or

(2)

where and is a cell in . The finite bounds are continuous semialgebraic functions on . The lower bound of the first form may also be , and its upper bound may be , with throughout . The second form requires a finite-valued .

For a finite set of polynomials, a decomposition is called -invariant if every polynomial in has a constant sign, positive, negative, or zero, on each cell. Such a decomposition of can be computed algorithmically. Any Boolean function of the corresponding polynomial equalities and inequalities then has a constant truth value on each cell, so its solution set is a union of cells. The cylindrical structure makes this useful for quantifier elimination.

For example, the open ball

(3)

is a single cell described by the simultaneous inequalities

(4)

The figure above shows a decomposition of the unit circle into four cells, the two endpoint cells and together with the two arcs

(5)

The two arcs have the same projection onto the -axis, the open interval . The endpoint cells project onto and . These lower-dimensional cells are needed to include the entire boundary of the closed disk. Reversing the coordinate order instead separates the top and bottom endpoints (Trott 2006).

A three-dimensional example comes from integration over a regular octahedron of unit edge length, with vertices and . The coordinate planes split its interior into eight congruent full-dimensional cells. The figure above shows their closures separated for visibility and one cell with its projection onto the -plane. The positive-octant cell has bounds

(6)

Lower-dimensional cells complete the decomposition on the splitting planes and boundary. They have zero volume and do not affect these volume integrals.

For a point chosen from the uniform distribution on , the mean of its Euclidean distance from the origin is

(7)

where is the volume. Replacing the integrand by gives the mean distance from the -axis. The factor 8 uses reflection symmetry of both the region and the integrand.

A planar slice of the integration for triangle triangle picking is illustrated above by fixing two of the chosen points at and in the triangle . For the moving point , the signed triangle area is

(8)

The three full-dimensional cells shown are

			(9)
			(10)
			(11)

The determinant has negative sign on and and positive sign on . The absolute value in the integrand can therefore be replaced by the appropriate signed expression on each cell. The vertical split at makes the projections of the cells onto the -axis identical or disjoint. Lower-dimensional cell boundaries have zero area. The full picking integral ranges over all six vertex coordinates.

A generic cylindrical algebraic decomposition describes the full-dimensional behavior of a semialgebraic set, allowing differences on an exceptional set of lower dimension. For example, a generic decomposition of the closed disk can retain the open disk and omit its boundary. The unit circle alone has no full-dimensional cell in .

The command CylindricalDecomposition[ineqs, x1, x2, ...] performs cylindrical algebraic decompositions in the Wolfram Language. Although the process is algorithmic, it can become computationally expensive as the number of variables increases.