hide
Free keywords:
-
Abstract:
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.
