Space-efficient planar convex hull algorithms

Written with J. Iacono, J. Katajainen, P. Morin, J. Morrison, and G. Toussaint.

Journal version (TCS)
Version presented at LATIN'02, under the title Optimal in-place planar convex hull algorithms

Abstract: We present in-place and in situ algorithms for computing 2d convex hulls. These algorithms can be viewed as a generalization of sorting where some points are not part of the output. All algorithms proposed in the literature use up to O(n) extra storage. In contrast, we explain how to implement or modify some algorithms, in order to work with the original storage plus O(1) (for in-place) or O(log n)( for in situ) extra storage. Our algorithms run in O(n) time and moves is the input is sorted along a direction, or worst-case O(n log h) time and moves. They are able to handle larger problems in main memory. Furthermore, as most in-place algorithms, they are likely to exhibit good cache behavior.

Related publications

Inplace convex hull of a polygonal line in linear time, with T. Chan.
Towards in-place geometric algorithms and data structures, with T. Chan, and E. Chen.