de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Interval analysis yields efficient dynamic filters for computational geometry

MPG-Autoren
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;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-37AC-F
Zusammenfassung
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.