This paper is concerned with floating-point filters for a two dimensional orientation problem which is a basic problem in the field of computational geometry. If this problem is only approximately solved by floating-p...
详细信息
This paper is concerned with floating-point filters for a two dimensional orientation problem which is a basic problem in the field of computational geometry. If this problem is only approximately solved by floating-point arithmetic, then an incorrect result may be obtained due to accumulation of rounding errors. A floating-point filter can quickly guarantee the correctness of the computed result if the problem is well-conditioned. In this paper, a simple semi-static floating-point filter which handles floating-point exceptions such as overflow and underflow by only one branch is developed. In addition, an improved fully-static filter is developed.
Geometric predicates are at the core of many algorithms, such as the construction of Delaunay triangulations, mesh processing and spatial relation tests. These algorithms have applications in scientific computing, geo...
详细信息
Geometric predicates are at the core of many algorithms, such as the construction of Delaunay triangulations, mesh processing and spatial relation tests. These algorithms have applications in scientific computing, geographic information systems and computer-aided design. With floating-point arithmetic, these geometric predicates can incur round-off errors that may lead to incorrect results and inconsistencies, causing computations to fail. This issue has been addressed using a combination of exact arithmetic for robustness and floating-point filters to mitigate the computational cost of exact computations. The implementation of exact computations and floating-point filters can be a difficult task, and code generation tools have been proposed to address this. We present a new C++ meta-programming framework for the generation of fast, robust predicates for arbitrary geometric predicates based on polynomial expressions. We combine and extend different approaches to filtering, branch reduction, and overflow avoidance that have previously been proposed. We show examples of how this approach produces correct results for data sets that could lead to incorrect predicate results with naive implementations. Our benchmark results demonstrate that our implementation surpasses state-of-the-art implementations.
Consider the computation of deciding relative orientations of objects undergoing multiple translations and rotations. Such an orientation test involves the computation of expressions based on arithmetic operations, sq...
详细信息
Consider the computation of deciding relative orientations of objects undergoing multiple translations and rotations. Such an orientation test involves the computation of expressions based on arithmetic operations, square roots and trigonometric functions. The computation of signs of such expressions using double precision floating-point arithmetic in modern computers may result in errors. In this article we demonstrate the existence of examples where double precision is not sufficient to compute the correct sign of an expression. We consider (i) simple expressions involving only the four basic arithmetic operations, (ii) expressions involving the square-root function and (iii) expressions representing orientation tests in two- and three-dimensions involving objects undergoing arbitrary rotations by angles given in radians, thereby requiring the computation of trigonometric functions. We develop a system that uses requisite high precision for computing the correct sign of such expressions. The system uses our floating-point filter called L-filter and the bigfloat extended precision package in LEDA (Library of Efficient Data Types and Algorithms).
We discuss floating-point filters as a means of restricting the precision needed fur arithmetic operations while still computing the exact result. We show that interval techniques can be used to speed up the exact eva...
详细信息
We discuss floating-point filters as a means of restricting the precision needed fur arithmetic operations while still computing the exact result. We show that interval techniques can be used to speed 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 Standard 754. Using this approach we engineer an efficient floating-point filter for the computation of the sign of a determinant that works for arbitrary dimensions, We validate our approach experimentally, comparing it with other static, dynamic and semi-static filters. (C) 2001 Elsevier Science B.V. All rights reserved.
In this paper we talk about a new efficient numerical approach to deal with inaccuracy when implementing geometric algorithms. Using various floating-point filters together with arbitrary precision packages, we develo...
详细信息
In this paper we talk about a new efficient numerical approach to deal with inaccuracy when implementing geometric algorithms. Using various floating-point filters together with arbitrary precision packages, we develop an easy-to-use expression compiler called EXPCOMP. EXPCOMP supports all common operations +, -, ., /, root. Applying a new semi-static filter, EXPCOMP combines the speed of static filters with the power of dynamic filters. The filter stages deal with all kinds of floating-point exceptions, including underflow. The resulting programs show a very good runtime behaviour.
We present the design of the Boost interval arithmetic library, a C++ library designed to handle mathematical intervals efficiently and in a generic way. Interval computations are an essential tool for reliable comput...
详细信息
We present the design of the Boost interval arithmetic library, a C++ library designed to handle mathematical intervals efficiently and in a generic way. Interval computations are an essential tool for reliable computing. Increasingly a number of mathematical proofs have relied on global optimization problems solved using branch-and-bound algorithms with interval computations, it is therefore extremely important to have a mathematically correct implementation of interval arithmetic. Various implementations exist with diverse semantics. Our design is unique in that it uses policies to specify three independent variable behaviors: rounding, checking, and comparisons. As a result, with the proper policies, our interval library is able to emulate almost any of the specialized libraries available for interval arithmetic, without any loss of performance nor sacrificing the ease of use. This library is openly available at ***. (c) 2005 Elsevier B.V. All fights reserved.
暂无评论