An in-place Quickhull algorithm
摘要
Finding the convex hull of a point set in a two-dimensional plane is one of the fundamental problems and applications in spatial databases, geographical information systems, and computational geometry. Because of the demand for space-efficient main memory algorithms (e.g., for big spatial data processing) and the important role that convex hull algorithms play in geospatial applications, there is a pressing need to develop in-place versions of existing convex hull algorithms. The original Quickhull algorithm is well known as a powerful but out-of-place convex hull algorithm. In this paper, we devise two new versions of it, a space-saving version and an in-place version, and compare them against the only other existing space-efficient Quickhull algorithm so far. We identify the problems why the existing space-efficient Quickhull algorithm cannot be an in-place algorithm and introduce our solution to overcoming them. We demonstrate that our algorithms are competitive in terms of run time and space requirements, even though they use less main memory space than the others.