A Survey of Approximate Convex Hull Algorithms

12:00pm, Feb 10, Tuesday, 2009, ST2, 430

Speaker

Raheem Rufai
Department of Computer Science
George Mason University

Abstract The convex hull of a point set S , often denoted as conv(S), is the smallest convex set that contains S. This essentially means that a line connecting any pair of vertices in S is enclosed by conv(S). This talk will introduce the convex hull problem and briefly survey existing state of the art for exact algorithms. The crux of the discussion, however, will focus on the current state of affairs of approximation algorithms for the convex hull. The talk might also touch upon related issues such as kinetization and dynamization of these algorithms and the core-set framework as time permits.

Short Bio Raimi Rufai is a doctoral student in the CS Department, George Mason University. His research interests span Computational Geometry, Software Engineering and enterprise software development and modeling. He is currently working on his dissertation in Computational Geometry under the tutelage of Prof. Dana Richards.