Steven Fortune, Christopher J. Van Wyk  Home/Search
Context Related
| belllabs.com/cm/cs/w...sayeeiacg.ps.gz Cached: PS.gz PS PDF DjVu Image Update Help From: belllabs.com/cm/cs/who/sj...pubs (more) Homepages: S.Fortune [2] HPSearch (Update Links) |
Rate this article:      (best)Comment on this article |
Abstract: Geometric algorithms are usually described assuming that arithmetic operations are performed exactly on real numbers. A program implemented using a naive substitution of floating-point arithmetic for real arithmetic can fail, since geometric primitives depend upon sign-evaluation and may not be reliable if evaluated approximately. Geometric primitives are reliable if evaluated exactly with integer arithmetic, but this degrades performance since software extended-precision arithmetic is... (Update)
Context of citations to this paper: More
.... class more efficient is the use of LEDA s primitive predicates (e.g. orientation) that are implemented using floating point filters [9, 20] which speed up the exact computation. This traits class could not be made a special case of Pmsegmentexacttraits R since the usage of...
.... resolve it otherwise (or if we pass some user defined threshold) In this sense our scheme resembles the adaptive arithmetic schemes [11, 22] that work with floating point approximations (such as interval arithmetic) and resort to (slow) exact arithmetic only when the...
Cited by: More
A Performance Comparison of Interval Arithmetic and Error.. - Seshia, Blelloch (2001) (Correct)
Efficient algorithms for line and curve segment.. - Boissonnat, Snoeyink (1999) (Correct)
An Adaptable and Extensible Geometry Kernel - Hert, Hoffmann, Kettner, Pion.. (Correct)
Active bibliography (related documents): More All
1.2: Robustness issues in geometric algorithms - Fortune (1996) (Correct)
1.1: The Exact Computation Paradigm - Yap, Dubé (1994) (Correct)
0.6: Polyhedral Modeling With Multiprecision Integer Arithmetic - Fortune (1996) (Correct)
Similar documents based on text: More All
0.2: Efficient Exact Arithmetic for Computational Geometry - Fortune, Van Wyk (1993) (Correct)
0.1: Extracting Geometric Information from Architectural Drawings - Brian Kernighan (Correct)
0.1: An Experiment Using LN for Exact Geometric Computations - Chang, Milenkovic (1993) (Correct)
Related documents from co-citation: More All
7: Adaptive precision floating-point arithmetic and fast robust geometric predicate.. (context) - SHEWCHUK - 1997
7: Exact geometric computation in LEDA - Burnikel, Konnemann et al. - 1995
7: The problems of accuracy and robustness in geometric computation (context) - Hoffmann - 1989
BibTeX entry: (Update)
S. FORTUNE AND C. J. VAN WYK, Static Analysis Yields Efficient Exact Integer Arithmetic for Computational Geometry, ACM Trans. Graph. 15(3) (1996) July, 223--248. http://citeseer.nj.nec.com/fortune96static.html More
@article{ fortune96static,
author = "Steven Fortune and Christopher J. {Van Wyk}",
title = "Static analysis yields efficient exact integer arithmetic for computational geometry",
journal = "ACM Transactions on Graphics",
volume = "15",
number = "3",
pages = "223--248",
year = "1996",
url = "citeseer.nj.nec.com/fortune96static.html" }
Citations (may not include all citations):413 Algorithms in Combinatorial Geometry (context) - Edelsbrunner - 1987
216 Primitives for the manipulation of general subdivisions and .. (context) - Guibas, Stolfi - 1985
133 Algorithms for reporting and counting geometric intersection.. (context) - Bentley, Ottmann - 1979
100 IEEE std (context) - for, point et al. - 1987
51 Towards exact geometric computation - Yap - 1993
50 Efficient exact arithmetic for computational geometry - Fortune, Van Wyk - 1993
50 Finite-resolution computational geometry (context) - Greene, Yao - 1986
35 Efficient Delaunay triangulation using rational arithmetic (context) - Karasick, Lieber et al. - 1990
30 How to compute the Voronoi diagram of line segments: theoret.. (context) - Burnikel, Mehlhorn et al. - 1994
27 second edition (context) - Yap, Dub'e et al. - 1995
26 Safe and effective determinant evaluation - Clarkson - 1992
25 Constructing strongly convex hulls using exact or rounded ar.. - Li, Milenkovic - 1990
25 Numerical stability of algorithms for 2d Delaunay triangulat.. (context) - Fortune
18 Construction of the Voronoi diagram for one million generato.. (context) - Sugihara, Iri - 1989
15 Error-free boundary evaluation based on a lazy rational arit.. - Benouamer, Michelucci et al.
14 A solid modeling system free from topological inconsistency (context) - Sugihara, Iri - 1989
12 Rounding face lattices in the plane (context) - Milenkovic - 1989
12 BigNum: a portable and efficient package for arbitrary-preci.. - Serpette, Vuillemin et al. - 1989
11 Practical segment intersection with finite precision output - Hobby - 1993
9 On Properties of Floating Point Arithmetics: Numerical Stabi.. - Priest - 1993
9 Progress in computational geometry (context) - Fortune - 1993
7 Programming Style (context) - Cargill - 1992
7 A basis for implementing exact geometric algorithms (context) - Dub'e, Yap - 1994
7 LN users manual (context) - Fortune, Van Wyk - 1993
6 Implementation of a sweepline algorithm for the straight lin.. - Mehlhorn, Naher - 1994
5 An experiment using LN for exact geometric computations - Chang, Milenkovic - 1993
5 solution to imprecision in computational geometry (context) - Benouamer, Jaillon et al. - 1993
5 Polyhedral modelling with exact arithmetic (context) - Fortune - 1995
4 Geometric and Solid Modelling: an Introduction (context) - Hoffmann - 1989
4 a la saisie d (context) - Jaillon, arithm'etique et al. - 1993
2 a Fortran multiple-precision arithmetic (context) - Brent, MP - 1978
2 The LEDA user manual, Version 3.1, January 16, 1995. LEDA is.. (context) - Naher - 1995
1 Plane sweep with efficient exact arithmetic (context) - Van Wyk - 1994
1 Missing real numbers (context) - Van Wyk - 1995
1 Evaluation of a method to compute the sign of determinants (context) - Avnaim, Boissonat et al. - 1995
The graph only includes citing articles where the year of publication is known.
Documents on the same site (http://cm.bell-labs.com/cm/cs/who/sjf/pubs.html): More
Topological beam tracing - Fortune (1999) (Correct)
Robustness issues in geometric algorithms - Fortune (1996) (Correct)
Voronoi Diagrams and Delaunay Triangulations - Fortune (1992) (Correct)
Online articles have much greater impact More about CiteSeer Add search form to your site Submit documents Feedback
CiteSeer - citeseer.org - Terms of Service - Privacy Policy - Copyright © 1997-2002 NEC Research Institute