MPI-I-96-1-016

We specify and implement a kernel for computational geometry in arbitrary finite dimensional space. The kernel provides points, vectors, directions, hyperplanes, segments, rays, lines, affine transformations, and operations connecting these types. Points have rational coordinates, hyperplanes have rational coefficients, and analogous statements hold for the other types. We therefore call our types \emph{rat\_point}, \emph{rat\_vector}, \emph{rat\_direction}, \emph{rat\_hyperplane}, \emph{rat\_segment}, \emph{rat\_ray} and \emph{rat\_line}. All geometric primitives are \emph{exact}, i.e., they do not incur rounding error (because they are implemented using rational arithmetic) and always produce the correct result. To this end we provide types \emph{integer\_vector} and \emph{integer\_matrix} which realize exact linear algebra over the integers. The kernel is submitted to the CGAL-Consortium as a proposal for its higher-dimensional geometry kernel and will become part of the LEDA platform for combinatorial and geometric computing.