MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Brönnimann, Hervé
Burnikel, Christoph
Pion, Sylvain		dblp
dblp
dblp
Editor(s):
BibTeX cite key*:
BBP:SCG98
Title, Booktitle
Title*:
Interval analysis yields efficient dynamic filters for computational geometry
Booktitle*:
Proceedings of the 14th International Annual ACM Symposium on Computational Geometry (SCG-98)
Event, URLs
Conference URL::
http://www.cs.umn.edu/scg98/
Downloading URL:
Event Address*:
Minneapolis, Minnesota
Language:
English
Event Date*
(no longer used):
June 7-10, 1998
Organization:
Association Computing Machinery (ACM)
Event Start Date:
21 September 2023
Event End Date:
21 September 2023
Publisher
Name*:
ACM Press
URL:
Address*:
New York, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
14
Month:
June
Pages:
165-174
Year*:
1998
VG Wort Pages:
ISBN/ISSN:
0-89791-973-4
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) 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.
Keywords:
Computational geometry, interval arithmetic, determinants, linear systems, simplex algorithm
Download
Access Level:

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
experts only
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat



BibTeX Entry:

@INPROCEEDINGS{BBP:SCG98,
AUTHOR = {Br{\"o}nnimann, Herv{\'e} and Burnikel, Christoph and Pion, Sylvain},
 TITLE = {Interval analysis yields efficient dynamic filters for computational geometry},
 BOOKTITLE = {Proceedings of the 14th International Annual ACM Symposium on Computational Geometry (SCG-98)},
 PUBLISHER = {ACM Press},
 YEAR = {1998},
 ORGANIZATION = {Association Computing Machinery (ACM)},
 NUMBER = {14},
 PAGES = {165--174},
 ADDRESS = {Minneapolis, Minnesota},
 MONTH = {June},
 ISBN = {0-89791-973-4},
}

Entry last modified by Uwe Brahm, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Christoph Burnikel		Created
03/02/1999 14:36:57
Revisions
4.
3.
2.
1.
0.		Editor(s)
Uwe Brahm
Uwe Brahm
Uwe Brahm
Uwe Brahm
Uwe Brahm		Edit Dates
01.04.99 09:38:21
01.04.99 09:33:47
29.03.99 17:08:04
29.03.99 16:54:06
02/03/99 14:36:57