Method of orienting curves for determining the convex hull of a finite set of points in the plane

Abstract

In this article, we present an efficient algorithm to determine the convex hull of a finite planar set using the idea of the Method of Orienting Curves (introduced by Phu in Zur Lösung einer regulären Aufgabenklasse der optimalen Steuerung in Großen mittels Orientierungskurven, Optimization, 18 (1987), pp. 65–81, for solving optimal control problems with state constraints). The convex hull is determined by parts of orienting lines and a final line. Two advantages of this algorithm over some variations of Graham's convex hull algorithm are presented.

Keywords:

• method of orienting curves
• convex hull
• Graham's convex hull algorithm

Acknowledgements

The author gratefully acknowledges the many helpful suggestions of Professor Hoang Xuan Phu during the preparation of the article, and the author has responsibility for any remaining errors. Part of the article was written at the Interdisciplinary Center for Scientific Computing (IWR), University of Heidelberg, Germany, during the author's stay there. He wishes to thank Professor Dr. H.C. Hans Georg Bock and Dr. Johannes P. Schlöder for the invitation and hospitality.