Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


A computational basis for higher-dimensional computational geometry

Mehlhorn, Kurt and Näher, Stefan and Schirra, Stefan and Seel, Michael and Uhrig, Christian

MPI-I-96-1-016. May 1996, 120 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.

References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s): KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Mehlhorn, Kurt and N{\"a}her, Stefan and Schirra, Stefan and Seel, Michael and Uhrig, Christian},
  TITLE = {A computational basis for higher-dimensional computational geometry},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-96-1-016},
  MONTH = {May},
  YEAR = {1996},
  ISSN = {0946-011X},