Print version record.

This undergraduate and postgraduate text will familiarise readers with interval arithmetic and related tools to gain reliable and validated results and logically correct decisions for a variety of geometric computations plus the means for alleviating the effects of the errors. It also considers computations on geometric point-sets, which are neither robust nor reliable in processing with standard methods. The authors provide two effective tools for obtaining correct results: (a) interval arithmetic, and (b) ESSA the new powerful algorithm which improves many geometric computations and makes them rounding error free. Familiarises the reader with interval arithmetic and related tools to gain reliable and validated results and logically correct decisions for a variety of geometric computationsProvides two effective methods for obtaining correct results in interval arithmetic and ESSA.

Front Cover; ABOUT OUR AUTHORS; Geometric Computations with Interval and New Robust Methods: Applications in Computer Graphics, GIS and Computational Geometry; Copyright Page; Table of Contents; List of Figures; List of Tables; Preface; Chapter 1. Introduction; 1.1 Errors in Numerical Computations; 1.2 Geometric Computations; 1.3 Problems in Geometric Computations Caused by Floating Point Computation; 1.4 Approaches to Controlling Errors in Geometric Computations; 1.5 The Interval Analysis Approach; 1.6 Global Interval Aspects; 1.7 The Exact Sign of Sum Algorithm (ESSA).

1.8 Arithmetic Filters1.9 Computer Implementations; Chapter 2. Interval Analysis; 2.1 Introduction; 2.2 Motivation for Interval Arithmetic; 2.3 Interval Arithmetic Operations; 2.4 Implementing Interval Arithmetic; 2.5 Further Notations; 2.6 The Meaning of Inclusions for the Range; 2.7 Inclusion Functions and Natural Interval Extensions; 2.8 Combinatorial Aspects of Inclusions; 2.9 Skelboe's Principle; 2.10 Inner Approximations to the Range of Linear Functions; 2.11 Interval Philosophy in Geometric Computations; 2.12 Centered Forms and Other Inclusions; 2.13 Subdivision for Range Estimation.

2.14 SummaryChapter 3. Interval Newton Methods; 3.1 Introduction; 3.2 The Interval Newton Method; 3.3 The Hansen-Sengupta Version; 3.4 The Existence Test; Chapter 4. The Exact Sign of Sum Algorithm (ESSA); 4.1 Introduction; 4.2 The Need for Exact Geometric Computations; 4.3 The Algorithm; 4.4 Properties of ESSA; 4.5 Numerical Results; 4.6 Merging with Interval Methods, Applications; 4.7 ESSA and Preprocessing Implementation in C; Chapter 5. Intersection Tests; 5.1 Introduction; 5.2 Line Segment Intersections; 5.3 Box-Plane Intersection Testing; 5.4 Rectangle-Triangle Intersection Testing.

5.5 Box-Tetrahedron Intersection Testing5.6 Ellipse-Rectangle Intersection Testing; 5.7 Intersection Between Rectangle and Explicitly Defined Curve; 5.8 Box-Sphere Intersection Test; Chapter 6. The SCCI-Hybrid Method for 2D-Curve Tracing; 6.1 Introduction; 6.2 The Parts of the SCCI-Hybrid Method; 6.3 Examples; Chapter 7. Interval Versions of Bernstein Polynomials, Bézier Curves and the de Casteljau Algorithm; 7.1 Introduction; 7.2 Plane Curves and Bernstein Polynomials; 7.3 Interval Polynomials and Interval Bernstein Polynomials; 7.4 Real and Interval Bézier Curves.

7.5 Interval Version of the de Casteljau AlgorithmChapter 8. Robust Computations of Selected Discrete Problems; 8.1 Introduction; 8.2 Convex-Hull Computations in 2D; 8.3 Exact Computation of Delaunay and Power Triangulations; 8.4 Exact and Robust Line Simplification; Bibliography; Index.

Elsevier ScienceDirect All Books