MPI-INF/SWS Research Reports 1991-2021

1. Author,Editor - 3. with BibTeX cite keys


A computational basis for higher-dimensional computational geometry

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

May 1996, 120 pages.

Status: available - back from printing

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.

  • Attachement: (523 KBytes)

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},