Exact Computation of 4-D Convex Hulls with Perturbation and Acceleration

An incremental algorithm for constructing the four-dimensional convex hull is implemented using exact arithmetic together with the symbolic perturbation technique. Exact judgement of the topological structure of the four-dimensional convex hull requires about four times higher precision than the input. To decrease this computational cost, the lazy evaluation scheme is used. Experiments show that the computation can be accelerated more than one hundred times for non-degenerate input and more than three times even for highly degenerate input.