Edinburgh Research Explorer

The convex hull in a new model of computation

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Related Edinburgh Organisations

Open Access permissions



Original languageEnglish
Title of host publicationProceedings of the 13th Canadian Conference on Computational Geometry, University of Waterloo, Ontario, Canada, August 13-15, 2001
Number of pages4
Publication statusPublished - 2001


We present a new model of geometric computation which supports the design of robust algorithms for exact real number input as well as for input with uncertainty, i.e. partial input. In this framework, we show that the convex hull of N computable real points in R^d is indeed computable. We provide a robust algorithm which, given any set of N partial inputs, i.e. N dyadic or rational rectangles, approximating these points, computes the partial convex hull in time O(N log N) in 2d and 3d. As the rectangles are refined to the N points, the sequence of partial convex hulls converges effectively both in the Hausdorff metric and the Lebesgue measure to the convex hull of the N points.

Download statistics

No data available

ID: 25070385