The convex hull in a new model of computation

Abbas Edalat, André Lieutier, Elham Kashefi

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

Abstract

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.
Original languageEnglish
Title of host publicationProceedings of the 13th Canadian Conference on Computational Geometry, University of Waterloo, Ontario, Canada, August 13-15, 2001
Pages93-96
Number of pages4
Publication statusPublished - 2001

Fingerprint Dive into the research topics of 'The convex hull in a new model of computation'. Together they form a unique fingerprint.

Cite this