A New Convex Hull Algorithm for Planar Sets

WILLIAM F. EDDY
Carnegie-Mellon University

A new algorithm, CONVEX, that determines which points of a planar set are vertices of the
convex hull of the set is presented. It is shown that CONVEX operates in a fashion similar
to the sorting algorithm QUICKERSORT. Evidence is given which indicates that in some
situations CONVEX is preferable to earlier algorithms. A Fortran implementation, intended
to minimize execution time, is presented and an alternative, which minimizes storage require-
ments, is discussed.
Key Words and Phrases: convex hull, QUICKERSORT, partitioning, sorting
CR Categories: 5.30, 5.31
The Algorithm: CONVEX, A New Convex Hull Algorithm for Planar Sets. AOM Trans.
Math. ~qoftware$, 4 (Dee. 1977), 411-412.

INTRODUCTION
The convex hull of a planar set is the minimum-area convex polygon containing
the planar set. A convex polygon is clearly determined b y its vertices. G r a h a m [1]
suggests an algorithm for determining which points of a planar set are vertices of
its convex hull. Because his algorithm requires sorting the points, if there are N
points then at least O(N log N) operations are needed to determine the vertices.
Recently, Preparata and Hong [3, 4] have shown t h a t there exist sets of points for
which every algorithm requires at least O(N log N) operations t o determine the
vertices of the convex hull. Jarvis [2] gives an algorithm which requires O(N.C)
operations, where C is the number of vertices. For some configurations of the
points in the plane (those with small values of C) the algorithm given b y Jarvis
will be faster than the algorithm of Graham; for other configurations it m a y be
slower. An adaptive algorithm, CONVEX, is presented here which never requires
more than O(N.C) operations to determine the vertices of the convex hull and
m a y require substantially fewer. However, C O N V E X m a y require more opera-
tions t h a n Graham's algorithm for some configurations of points. Evidence is
presented which suggests t h a t in applications C O N V E X is preferable to the "sort-
ing" algorithms [1, 3, 4] and to Jarvis's algorithm [2].

METHOD
Operationally, this algorithm is analogous to the sorting algorithm Q U I C K E R S O R T
[5]. At each step Q U I C K E R S O R T partitions the input array with respect to a

Copyright (~) 1977, Association for Computing Machinery, Inc. General permission to re-
publish, but not for profit, all or part of this material is granted provided that ACM's copy-
right notice is given and that reference is made to the publication, to its date of issue, and
to the fact that reprinting privileges were granted by permission of the Association for Com-
puting Machinery.
This research was supported in part by the National Science Foundation under Grant DCR75-
08374.
Author's address: Department of Statistics, Carnegie-Mellon University, Scheuley Park,
Pittsburgh, PA 15213.
ACM Ttauaactions on MathematicalSoftware.Vol.3. No. 4. Deoember1977.Pageo398-403.
 A New Convex Hull Algorithm for Planar Sets • 399

particular point and yields two output arrays, one containing those elements of
the input array which are smaller than the point and the other containing those
elements which are larger. QUICKERSORT continues to partition the subarrays
until subarrays of length 1 are obtained. CONVEX partitions the input array
with respect to a particular line, yielding two arrays of points. For convenience
the two sides of the partitioning line will be referred to as "above" and "below."
The key to the speed of CONVEX is that not every subarray need be partitioned.
Consider the points inside a triangle with vertices which are vertices of the convex
hull; these points cannot be vertices of the convex hull. It is possible to eliminate
these points from further consideration by choosing the partitioning lines to be
sides of such a triangle.

TREE REPRESENTATION
This algorithm may be interpreted as a preorder traversal of a particular binary
tree. The root of the tree represents the original set of points. The left son of each
node of the tree represents the subset of points above a partitioning line and the
right son represents the subset below. The leaves of the tree represent either null
subsets or subsets inside a triangle whose vertices are vertices of the convex hull.
On the left half of the tree left sons are visited first; on the right half of the tree
right sons are visited first.

PARTITIONING
At each step the subset of points represented by the current node of the tree is
partitioned by algorithm SPLIT. As input, SPLIT requires a line joining two ver-
tices of the convex hull and a set of points distinct from these vertices. It produces
as output (1) the subset A of points above the line, (2) the point farthest above the
line if A ~ 0 (the empty set), (3) the subset B of points below the line, and (4)
the point farthest below the line if B ~ 0. If the equation of the line is Z ( X , Y )
= a -{- b X -t- Y = O, then Z(Xo, Yo) determines for a point (X0, Y0) its position
relative to the line. Points which lie on the line are not vertices of the convex hull
and may be neglected in succeeding computations. The initial partitioning line
joins any two vertices; for simplicity they are chosen to be the points with mini-
mum and maximum X-coordinates.
AN EXAMPLE
In order to clarify the operation of this algorithm, the following example is pre-
sented. Figure 1 displays a planar set of points, the input to the algorithm. Only
those points which are important to the operation of the algorithm, the output
vertices of the convex hull, have been labeled. Table I presents in order the input
and output of successive partitioning steps with a legend describing the different
subsets of points. Figure 2 is the associated binary tree.

SPEED OF COMPUTATION
The number of operations required by this algorithm is of the same order as the
total number of points at all the nodes of the binary tree; this is equal to the total
number of points passed to SPLIT. It is possible that the tree is of height N and
ACM Transactions on Mathematical Software, Vol. 3, No. 4, December 1977.
 400 • William I:. Eddy

E B

F A

Fig. 1. Sample input to CONVEX with vertices labeled and partitioning lines drawn

Table I. Successive Calls to SPLIT for Sample Points of Figure 1

(A dash indicates that the information is not relevant to the operation of the
algorithm.)

Input Output
Above Below
Subset Line
Subset Extreme Subset Extreme
1 AF 2 D 10 G
2 AD 3 B 7
3 AB 9 4
4 BD 5 C a
5 BC ¢ 6
6 CD ¢ ~
7 DF 8 E ~,
8 DE ¢ 9
9 EF ~ ~
I0 FG 11 --
U GA • --

Legend
Subset Subset
Points Points
number number
1 all 9 above DF, below DE
2 above AF 10 below F A
3 above AD 11 below FA, above F G
4 above AD, below AB ~ inside A ABD
5 above BD ~ inside A BCD
6 above BD, below BC ~ inside ~ ADF
7 above AF, below AD ~ inside A D E F
8 above D F • inside A AFG

h e n c e t h e r e a r e a t o t a l of N(N + 1 ) / 2 p o i n t s . C o n s i d e r , for e x a m p l e , t h e s e t of
p o i n t s w h i c h lie o n t h e b o u n d a r y of a circle a t angles 0, ~r, 7r/2, v / 4 , r / 8 , . . . .
I t is also possible t h a t t h e t r e e is of h e i g h t 1 a n d h e n c e t h e r e a r e o n l y N p o i n t s ,
if all t h e p o i n t s lie on a line.
E a c h t i m e a S P L I T is p e r f o r m e d e i t h e r (1) a n e w v e r t e x of t h e c o n v e x h u l l is
ACM Transactions on Mathen~ticalSoftware.Vol 3, N o ~, December1977
 A New Convex Hull Algorithm for Planar Sets • 401

Fig. 2. Binary tree of successive calls to SPLIT in Table I

found or (2) it is determined that the partitioning line is an edge of the convex
hull. Since the number of edges equals the number of vertices, say C, the total
number of operations required is certainly less than or equal to O(N. C) but this
upper bound may be extremely crude. It should be noted that if a point is not on
the convex hull then it must be passed to SPLIT at least three times before it
may be eliminated from consideration. Thus a practical lower bound for the total
number of points passed to SPLIT is 3N -~ O(1).
Since the time required by this algorithm depends on the particular configuration
of points, it seems natural to consider samples from different probability distribu-
tions. For points sampled from a circular Gaussian distribution, it is known [5]
that for sufficiently large N the E(C) is O(~/(log N)). In this case the crude bound
for the expected number of operations is O(N~/(log N)). For a sample from a
uniform distribution on the interior of a circle the E(C) is O(N1/~) for large N [5].
Here the crude bound becomes O(N4/a).
Pseudorandom samples were generated for sample sizes 10, 32, 100, 316, and
1000 for five distributions: (1) uniform on the boundary of a circle, (2) uniform on
ACM Transactions on Mathematical Software, Vol. 3, No. 4, December 1977
402 • William F. Eddy

Table II. Average Number of Operations for Nine Random Samples from
Each of Five Distributions
(Numbers in parentheses are estimated standard deviations of the averages. Bottom number
in each cell is average number of vertices. All numbers rounded to integers.)

on Uniform on Uniform on Uniform on Circular Circular

boundary of interior of interior of Gaussian exponential
circle circle square
10 23 (0) 21 (1) 21 (0) 21 (0) 21 (0)
10 5 6 5 5
32 145 (0) 98 (2) 99 (2) 93 (O) 90 (0)
32 9 9 8 7
100 707 (5) 343 (4) 330 (6) 305 (2) 299 (2)
100 15 12 9 8
316 2998 (7) 1153 (5) 1141 (24) 975 (7) 966 (9)
314" 22 15 11 9
1000 11913 (19) 3691 (10) 3616 (68) 3094 (18) 3021 (8)
958* 33 19 12 10
* These numbers artificially reduced due to truncation error; see "Implementation."

the interior of a circle, (3) uniform on the interior of a square, (4) circular Gaussian,
(5) circular (double) exponential. T h e fifth distribution has a density which is
proportional to exp ( v / ( X ~ + y2)); the conditional distribution on any ray from
the origin is standard exponential. The total number of points passed to S P L I T
and the number of vertices of the convex hull were recorded. Average values for 9
samples are given in Table II.
The b o t t o m number in each cell in Table I I is C, the average value of C. Notice
t h a t N . C grows more quickly, for each distribution, than the average number of
points passed to S P L I T (the upper number in each cell). Hence this algorithin is
an improvement on Jarvis's algorithm, at least for these situations. Notice also
that, except for the extreme case represented b y the first column, N log N grows
more quickly than the average number of points passed to S P L I T . Hence this
algorithm is an improvement on the "sorting" algorithms for these situations.
IMPLEMENTATION
The application for which this algorithm was originally intended requires repeated
use of the program on different subsets of a sample of only a few hundred points.
This suggested the use of indirect addressing and a liberal use of storage in an ef-
fort to increase the speed. A linked list is used to refer to vertices of the convex
hull allowing insertions to be made at fixed cost no m a t t e r how m a n y vertices have
been found. The following loop in the calling program will allow the transfer of
successive vertices (in counterclockwise order) from the array X to the array Y.
K = IL(1)
DO 1 I = 1, NH
J = IH(K)
Y(1, I) X(1, J)
=

Y(2, I) = X(2, J)
1 K = IL(K)
A different implementation of the algorithm is possible. T o minimize the use of
storage, data points could be rearranged in place in a manner similar to Q U I C K E R -
SORT. In fact, the vertices of the convex hull could be moved to the initial ele-
ACM Transactions on Mathematical Software, Vol. 3, No. 4, December 1977.
 A New Convex Hull Algorithm for Planar Sets • 403

ments of the data array. Then the only additional storage required would be for a
pushdown stack to store the pointers to subarrays not yet partitioned. For this
alternative implementation right sons (in the binary tree) would be visited first
on the left half of the tree and left sons first on the right half. There would prob-
ably be considerable loss in speed of execution. The program presented here re-
quired less than 11 seconds of CPU time on an IBM 370/158 (in BC mode) to
produce the first column of numbers in Table II. This time includes generating the
samples, printing the results, and all related calculations for what is admittedly
an extreme case.
The only difficulty which has arisen while using this program can be noted in the
last two cells of the first column in Table II. When the convex hull has a large
number of vertices, adjacent sides are nearly parallel and truncation (roundoff)
error can significantly affect the results. Increasing the precision of the arithmetic
alleviates this problem.
There are several configurations of points which are handled by the program
CONVEX in a special way. Whenever the input contains only one or two points
they are the vertices of the convex hull (unless they are identical in the case when
there are two). Whenever all the points lie on a vertical line, this is detected and
the two extremes are returned without any calls to SPLIT. Vertical boundaries are
given special treatment: (1) When the two points which determine the initial
partition are chosen, care is taken to assure that they are vertices and not just
boundary points. (2) When partitioning, SPLIT uses the information whether the
set being partitioned is above or below the initial partitioning line to determine
its output.
There is no feature inherent in the basic idea of this algorithm which prevents
implementation for dimensions higher than 2. However, because the vertices of
the convex hull in higher dimensions cannot be ordered, the programming details
will be considerably more complicated. Of course in higher dimensions the gains
to be made by this procedure are smaller; in fact, in N - 1 dimensions all N points
are vertices of the convex hull if they are linearly independent.

ACKNOWLEDGMENT
I would like to thank J.A. Hartigan and B.H. Margolin for helpful conversations.
C.L. Lawson pointed out several errors in the way the original program handled
special cases, suggested several test configurations, and made other valuable re-
marks.
REFERENCES
1. GRAHAM,R.L. An efficient algorithm for determining the convex hull of a planar set.
Inform. Proc. Letters I (1972), 132-133.
2. JARVlS, R.A. On the identification of the convex hull of a finite set of points in the plane.
Inform. Proc. Letters ~ (1973), 18-21.
3. PREPARATA,F.P., AND HONG, S.J. Convex hulls of finite planar and spatial sets of points.
Report R-682, Coordinated Science Lab., U. of Illinois, Urbana, HI., April 1975.
4. PR~.PARA~A,F.P., AND HONe, S.J. Convex hulls of planar and spatial sets of points. Ab-
stract 726-68-1, Notices A M 8 ~ (1975), A-596.
5. RAYNAUD,H. Sur l'enveloppe eonvexe des nuages de points aleatoires dans R a . I . J . Appl.
Prob. 7 (1970), 35-48.
6. ScowsN, R.S. Algorithm 271: Quickersort. Comm. ACM 8, 11 (1965), 669-670.

Received September 1975; revised June 1976 and January 1977

ACMTransactionson MathematicalSoftware,Vol.3, No. 4, December1977.