de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Interval analysis yields efficient dynamic filters for computational geometry

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44210

Burnikel,  Christoph
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45191

Pion,  Sylvain
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Brönnimann, H., Burnikel, C., & Pion, S. (1998). Interval analysis yields efficient dynamic filters for computational geometry. In Proceedings of the 14th International Annual ACM Symposium on Computational Geometry (SCG-98) (pp. 165-174). New York, USA: ACM Press.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-37AC-F
Abstract
We discuss interval techniques for speeding up the exact evaluation of geometric predicates and describe an efficient implementation of interval arithmetic that is strongly influenced by the rounding modes of the widely used IEEE 754 standard. Using this approach we engineer an efficient floating point filter for the computation of the sign of a determinant that works for arbitrary dimensions. Furthermore we show how to use our interval techniques for exact linear optimization problems of low dimension as they arise in geometric computing. We validate our approach experimentally, comparing it with other static, dynamic and semi-static filters.