doi:10.3850/978-981-08-5118-7_028

ABSTRACT

This paper is concerned with robustness problems in computational geometry,especially, a convex hull for a set of points on two-dimensional space. Floating point arithmetic is preferred to be used for calculating a convex hull in terms of computational performance. However, it may output a meaningless result due to accumulation of rounding errors. In this paper, it is discussed how to output the exact convex hull for floating-point data. Even if overflow or underflow in the floating-point computations is occurred, our method can output the exact convex hull. At the end of this paper, numerical examples are presented to show the efficiency of the proposed algorithm.

Keywords: Computational geometry, Robust algorithms.

© 2010 Professional Activities Centre, National University of Singapore