English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

A computational basis for higher-dimensional computational geometry

MPS-Authors
/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45100

Näher,  Stefan
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45391

Schirra,  Stefan
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45446

Seel,  Michael
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45646

Uhrig,  Christian
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Ressource
No external resources are shared
Fulltext (public)

MPI-96-1-016.pdf
(Any fulltext), 47MB

Supplementary Material (public)
There is no public supplementary material available
Citation

Mehlhorn, K., Näher, S., Schirra, S., Seel, M., & Uhrig, C.(1996). A computational basis for higher-dimensional computational geometry (MPI-I-1996-1-016). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-A163-1
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.