Line segment intersection testing. (English) Zbl 1080.65018
The authors test numerical algorithms for determining the line segment intersections. They claim to use “exact” arithmetic methods. No, these methods are not exact. Their algorithm is based on the 40 years old Gill-Möller (not Knuth) algorithm for the optimal correction of sum computation [cf. O. Möller, Nordisk Tidskr. Inform. Behandl. 5, 37–50 (1965; Zbl 0131.15805)] and on the algorithm by M. Pichat [Ph.D. Thèse, Univ. Grenoble (1976)] for the correction of product computation in floating-point arithmetic.
The use of the IEEE 754 denormalized standard and of the double precision is usual. To improve the precision it will be suitable to use the Bayley package for arbitrary length floating format and, parallel, the Cuyt-Verdonk (Anvers University) package of optimal precision in IEEE floating point calculations, but it seems then the authors ignore these developments. However, the methods proposed by the authors reduce the cost of the running time of the usual numerical methods commonly used in the last time.
The use of the IEEE 754 denormalized standard and of the double precision is usual. To improve the precision it will be suitable to use the Bayley package for arbitrary length floating format and, parallel, the Cuyt-Verdonk (Anvers University) package of optimal precision in IEEE floating point calculations, but it seems then the authors ignore these developments. However, the methods proposed by the authors reduce the cost of the running time of the usual numerical methods commonly used in the last time.
Reviewer: Jacek Gilewicz (Marseille)
MSC:
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
| 65B10 | Numerical summation of series |
| 65G50 | Roundoff error |
Keywords:
dot product summation; roundoff error correction; intersection testing for line segments; floating-point arithmetic; algorithmsCitations:
Zbl 0131.15805Software:
mctoolboxReferences:
| [2] | ANSI/IEEE (New York): IEEE Standard for Binary Floating-Point Arithmetic, Standard 754–1985, 1985. |
| [4] | Fortune, S., Wyk, C.: Efficient exact arithmetic for computational geometry. In: Proc. 9th Annual ACM Symp. on Computational Geometry, pp. 163–172 (1993). |
| [8] | Higham, N. J.: Accuracy and stability of numerical algorithms, 2nd ed. Philadelphia: SIAM 2002. · Zbl 1011.65010 |
| [10] | Knuth, D. E.: The art of computer programming, 3rd ed., vol 2: Seminumerical algorithms. Addison-Wesley 1998. · Zbl 0895.65001 |
| [13] | Milenkovic, V.: Double precision geometry: a general technique for calculating line and segment intersections using rounded arithmetic. In: Proc. 30th Annual Symp. on the Foundations of Computer Science, pp. 500–506 (1989). |
| [14] | Moore, R. E.: Interval analysis. Englewood Cliffs, NJ: Prentice-Hall 1966. · Zbl 0176.13301 |
| [16] | Priest, D. M.: On properties of floating point arithmetics: numerical stability and the cost of accurate computations. PhD thesis, Mathematics Department, University of California, Berkeley, CA, 1992. |
| [17] | Ramshaw, L.: CSL notebook entry: The braiding of floating point lines. Unpublished note. Xerox PARC, October 1982. |
| [23] | Zhu, Y.-K.: Yong, J.-H., Zheng, G.-Q.: A new distillation algorithm for floating-point summation. SIAM J. Sci. Comput. (2005) (accepted). · Zbl 1119.65300 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
