| The convex hull problem is an important problem in computational geometry with such diverse applications as clustering, robot motion planning, convex relaxation, image processing, collision detection, infectious disease tracking, nuclear leak tracking, extent estimation, among many others.;The convex hull is a well-studied problem with a large body of results and algorithms in a variety of contexts. In this thesis, we consider three contexts: when only an approximate convex hull is required, when the input points come from a (potentially unbounded) data stream, and when layers of concentric convex hulls are required.;The first context applies when input point sets may contain errors from noise or from rounding, or when the accuracy provided by exact algorithms are simply not required. This thesis proposes a framework for examining convex hull approximation algorithms so that they can be better compared. The framework is then used to assess a number of existing algorithms and new algorithms proposed in the thesis. This framework can help an engineer to select the most appropriate algorithm for their scenario and to analyze new algorithms for this problem. Moreover, our new algorithms exhibit better space, time, and error bounds than existing ones. The second context applies to a base station in a wireless sensor network that receives incoming input points and must maintain a running convex hull within a memory constraint. This thesis proposes a new streaming algorithm that processes each point in time O(log k) where k is the memory constraint, while maintaining very good accuracy.;And finally, the last context applies when all the convex layers are sought. This has a variety of applications from robust estimation to pattern recognition. Existing algorithms for this problem either do not achieve optimal O(n log n) runtime and linear space, or are overly complex and difficult to implement and use in practice. This thesis remedies this situation by proposing a novel algorithm that is both simple and optimal. The simplicity is achieved by independently computing four sets of monotone convex layers in O( n log n) time and linear space. These are then merged together in O(n log n) time. |
