A Simple Convex Layers Algorithm
Raimi A. Rufai1 and Dana S. Richards2

arXiv:1702.06829v2 [cs.CG] 16 Mar 2017

1

SAP Labs, 111 rue Duke, Suite 9000, Montreal QC H3C 2M1, Canada
raimi.rufai@sap.com
2
Department of Computer Science, George Mason University,
4400 University Drive MSN 4A5, Fairfax, VA 22030, USA
richards@cs.gmu.edu

Abstract. Given a set of n points P in the plane, the first layer L1 of
P is formed by the points that appear on P ’s convex hull. In general,
a
S point belongs to layer Li , if it lies on the convex hull of the set P \
j<i {Lj }. The convex layers problem is to compute the convex layers Li .
Existing algorithms for this problem either do not achieve the optimal
O (n log n) runtime and linear space, or are overly complex and difficult
to apply in practice. We propose a new algorithm that is both optimal
and simple. The simplicity is achieved by independently computing four
sets of monotone convex chains in O (n log n) time and linear space.
These are then merged in O (n log n) time.
Keywords: convex hull, convex layers, computational geometry

1

Introduction

Algorithms for the convex layers problem that achieve optimal time and space
complexities are arguably complex and discourage implementation. We give a
simple O (n log n)-time and linear space algorithm for the problem, which is
optimal. Our algorithm computes four quarter convex layers using a plane-sweep
paradigm as the first step. The second step then merges these in O (n log n)-time.
Formally, the convex layers, L(P ) = {L1 , L2 , · · · , Lk }, of a set P of n ≥ 3
points is a partition of P into k ≤ ⌈n/3⌉ disjoint subsets Li , i = 1, 2, · · · , k called
layers,Ssuch that each layer Li is the ordered3 set of vertices of the convex hull
of P \ j<i {Lj }. Thus, the outermost layer L1 coincides exactly with the convex
hull of P , conv(P ). The convex layers problem is to compute L(P ).
Convex layers have several applications in various domains, including robust
statistics, computational geometry, and pattern recognition.

2

Related Work

A brute-force solution to the convex layers
S problem is obvious—construct each
layer Li as the convex hull of the set P \ j<i Lj using some suitable convex hull
3

That is the layers are polygons not sets.

algorithm. The brute-force algorithm will take O(kn log n) time where k is the
number of the layers. We say this algorithm “peels off” a set of points one layer at
a time. This peeling approach is reminiscent of many convex layers algorithms.
Another general approach to this problem is the plane-sweep paradigm.
One of the earliest works to take the peeling approach is Green and Silverman
[3]. Their algorithm repeatedly invokes quickhull to extract a convex layer at
each invocation. This algorithm runs in O(n3 ) worst-case time, and O(n2 log n)
expected time.
Overmars and van Leeuwen’s [5] algorithm for this problem runs in O(n log2 n).
It is based on a fully dynamic data structure for maintaining a convex hull under arbitrary insertions and deletions of points. Each of these update operations
takes O(log2 n) time, since constructing the convex layers can be reduced to inserting all the points into the data structure in time O(n log2 n), marking points
on the current convex hull, deleting them, and then repeating the process for
the next layer. Since each point is marked exactly once and deleted exactly once,
these steps together take no more than O(n log2 n) time.
Chazelle’s [2] algorithm for this problem runs in O(n log n) time and O(n)
space, both of which are optimal. A new algorithm is discussed in Sect. 3.
(Chazelle [2] used a balanced tree approach as well as our new algorithm, but the
information stored in our tree corresponds to a very different set of polygonal
chains.)
The first algorithm on record that uses the plane-sweep approach is a modification of Jarvis march proposed by Shamos [6]. The algorithm works by doing
a radial sweep, changing the pivot along the way, just as in the Jarvis march,
but does not stop after processing all the points. It proceeds with another round
of Jarvis march that excludes points found to belong to the convex hull in the
previous iteration. This way, the algorithm runs in O(n2 ).
Nielsen [4] took advantage of Chan’s grouping trick [1] to obtain yet another
optimal algorithm for the convex layers problem. Nielsen’s algorithm is outputsensitive in that it can be parametrized by the number of layers l to be computed.
It runs in O(n log Hl ) time where Hl is the number of points appearing on the
first l layers.

3

New Algorithm

Our algorithm builds four sets of convex layers, each with a distinct direction
of curvature. The set of points P must be known ahead of time. For ease of
presentation, we will assume below that the points are in general position (no
three on a line and no two share a coordinate). Removing this assumption is easy
and our implementation does not make the assumption. Each point’s horizontal
ranking is precomputed by sorting the points using their x-coordinates.
A northwest monotone convex chain C = (p1 , p2 , · · · , pn ) has pi .x < pi+1 .x,
pi .y < pi+1 .y and no point in the chain is above the extended line through pi
and pi+1 , 1 ≤ i < n. The head (tail) of the chain C is defined as head(C) =
p1 (tail(C) = pn ). A full monotone convex chain is formed by augmenting

C = (p1 , p2 , · · · , pn ) with two fictional sentinel points, p0 = (p1 .x, −∞), and
pn+1 = (∞, pn .y). Note that given a full chain C, the calls head(C) and tail(C)
return p1 and pn and not the sentinels. The ∞’s are symbolic and the operations
are overloaded for them.
We call the chain northwest since it bows outward in that direction. Similarly
we will refer to a chain as southwest if it is northwest after rotating the point
set 90 degrees clockwise about the origin. Northeast and southeast are defined
analogously. Except in the section on merging below, all of our chains will be
northwest monotone convex chains, so we will simply call them chains.
We say a chain C1 precedes another chain C2 , if tail(C1 ).x < head(C2 ).x.
Additionally, we say a line is tangent to a chain, if it touches the chain and no
point in the chain is above the line.
Let chain C1 precede chain C2 . If tail(C1 ).y < tail(C2 ).y then a bridge
between the chains is a two-point chain (p1 , p2 ) where p1 is in chain C1 , p2
is in chain C2 and the line through p1 and p2 is tangent to both chains. If
tail(C1 ).y ≥ tail(C2 ).y then the chain (tail(C1 ), tail(C2 )) is a degenerate
bridge.
Let C = (p0 , p1 , p2 , · · · , pn , pn+1 ) be a full chain. C dominates a point p if p
is below the segment (pi , pi+1 ), for some 1 ≤ i ≤ n. A full chain C dominates a
full chain C ′ if C dominates every point of C ′ . The (northwest) hull of a point
set P , or just the hull chain of P , is the chain of points from P that dominates
every other point in P .
3.1

Hull Tree Data Structure

The hull tree T for the point set P , is a binary tree. T is either nil or has: a) A
root node that contains the hull chain for P , and b) A partition of the non-hull
points from P by some x coordinate into PL and PR . The left and right children
of the root are the hull trees T.L and T.R for PL and PR , respectively.
The root node contains the fields: a) T.hull is the full hull chain; b) T.l is a
cursor into the hull chain, that initially scans rightwards, and c) T.r is a cursor
into the hull chain, that initially goes leftwards.
The reason for the two cursors is so that we can be explicit about how the
hull chain is scanned. Our analysis depends on the claim that a point is only
scanned a constant number of times before being deleted from that chain. We
will maintain the invariant that T.l is never to the right of T.r. (For example,
if T.r coincides with T.l and T.r moves left then T.l will be pushed back to
maintain the invariant.)
As a preprocessing step, the points are sorted by x-coordinates and assigned
a 0-based integer rank, represented by a ⌈log n⌉ bit binary string. We will use
a perfectly balanced binary tree as the skeleton for our hull tree. It will have
n leaves with no gaps from left to right. The skeleton is only implicit in our
construction. The leaves will be associated with the points by rank from left to
right. We will use the conventional trick that the path from the root to a leaf
is determined by the binary representation of the rank of the leaf, going left on
0 and right on 1. We now specify PL as the set of points, not in the hull chain,

whose rank starts with 0 in binary and PR is analogous with a leading bit of 1.
We will say a point in, say, PL “belongs” to the subtree T.L.
As hull points are peeled off, the corresponding leaf nodes will become obsolete, but we never recalculate ranks. It follows that the skeleton of the tree
will always be of height ⌈log n⌉, even though, over time, more and more of the
bottom of the tree will become vacant. In addition to this invariant, we explicitly
mention these other invariants: (a) T.hull is a full northwest monotone convex
chain, (b) T.hull is the hull of P , (c) T.l.x ≤ T.r.x, and (d) T.L and T.R are the
hull trees for PL and PR .
Lemma 1. The space complexity of a hull-tree T for a set P of n points is
Θ (n).
Proof. The skeleton of the binary tree with n leaves clearly has O(n) nodes of
constant size. There is also the space for all the lists representing the various hull
chains. However, from the definitions of PL and PR , every point is on exactly
one hull chain. This completes the proof.
⊓
⊔
3.2

Tree Construction

The construction of the hull tree is done by repeated insertions into an initially
empty tree. The overall procedure is a plane-sweep algorithm, since the inserted
points will have increasing y-coordinates. We shall come back to the buildTree
routine after first looking into the insert algorithm.
3.2.1 insert. Algorithm insert is a recursive algorithm. Rather than insert
a single point at a time, we feel it is more natural to batch several such insertions
when we can first link them into a chain. It takes as input a chain C of vertices
and a hull tree T . Because insert will only be used in a plane-sweep manner,
we will be able to assume as a precondition that C is nonempty, no point in C
was previously inserted, and no point in C is dominated by the initial hull tree
of T .
We specify the procedure tangents(al , ar , T ) which assumes al .x < ar .x
al .y < ar .y and neither al nor ar is dominated by T.hull = (h0 , h1 , . . . , hk , hk+1 ).
It returns a pair of points (ql , qr ) each from T.hull. We require the line through
ql and al be a leftward tangent. If h1 .x < al .x and h1 .y < al .y, this is welldefined. Otherwise, we return a degenerate tangent with ql = h0 . Similarly, if
ar .x < hk .x and ar .y < hk .y, then qr defines a rightward tangent with ar .
Otherwise, we return qr = hk+1 .
We sketch the implementation of tangents. If the leftward tangent is welldefined, we compute ql by scanning from the current position of T.l. In constant
time we can determine if we should scan to the left or to the right. (As is standard
we keep track of the changing slopes of lines through al .) Similarly, if the tangent
is well-defined, we scan for qr using T.r.
Lemma 2. Algorithm insert correctly inserts C into T .

Algorithm 3.1: insert(C, T )

1
2
3
4
5
6
7
8
9
10
11

Input : C, a chain of points to be inserted into T ,
T , the hull tree for some point set P .
Output: T , the hull tree for P ∪ C.
if T = nil then
Create a root node with T.hull = C
T.l = head(C); T.r = tail(C)
else
(ql , qr ) = tangents(head(C), tail(C), T )
C ′ = the portion of T.hull strictly between ql and qr
Replace C ′ by C within T.hull
Scan and split C ′ to create these two chains
CL = {p ∈ C ′ | p belongs in T.L}; CR = {p ∈ C ′ | p belongs in T.R}
T.L = insert(CL , T.L) ; T.R = insert(CR , T.R)
return T

Proof. The proof is by induction on the number of points. The base case, where
T is empty, is clear. In general, we only need to establish that the new T.hull
is correct; this follows since all the points removed, in C ′ , are dominated by the
new hull. By the recursive definition of hull trees the points of C ′ now belong in
either T.L or T.R and are recursively inserted into those trees.
⊓
⊔

3.2.2 buildTree. Given a point set P , algorithm buildTree starts by
sorting these points by their x-coordinates. The 0-based index of a point p in
such a sorted order is called its rank. As discussed above, a point’s rank is used
to guide its descent down the hull tree during insertion.
Algorithm 3.2: buildTree(P )

1
2
3
4
5
6

Input : P , a set of points, {p1 , p2 , . . . , pn }.
Output: T , a hull tree built from P .
Compute the rank of each point in P by x-coordinate
Sort the points in P by increasing y-coordinate
Create an empty hull tree T
for each p in order do
insert(p, T )
return T

Recall that the insert procedure expects a hull chain as the first parameter,
so the call to insert in buildTree is a understood to be a chain of one vertex.
Note that such singleton chains satisfy the preconditions of insert. Once all the
points have been inserted, the hull tree is returned.
Lemma 3. Right after a point p is inserted into a hull tree T , tail(T.hull) = p.

Proof. Since points are inserted into T by increasing y-coordinate value, the
most recently inserted point must have the largest y coordinate value so far. So
it must be in the root hull and cannot have any point after it.
⊓
⊔
Lemma 4. Algorithm buildTree constructs a hull tree of a set of n points in
O (n log n) time.
Proof. Clearly the initial steps are within the time bound. It remains only to
show that all the invocations of insert take no more than O (n log n) time.
Consider an arbitrary point p inserted into T by buildTree. Initially, it
goes into the T.hull by Lemma 3. In subsequent iterations, the point either stays
within its current hull chain or descends one level owing to an eviction from its
current hull chain. The cost of all evictions from a chain C is dominated by the
right-to-left tangent scan. We consider the number of points we scan past (i.e.
not counting the points at the beginning and end of scan). Consider the cursor
T.l. It scans left to right past points once; if we scan past a point a second time,
going right to left, then that point will be in C ′ and will be evicted from this
level. Symmetric observations hold for T.r. And a point will be scanned a final
time if it is in CL or CR . Hence we will scan past a point a constant number of
times before it is evicted.
A call to insert takes constant time every time it is invoked (and it is only
invoked when at least one point has been evicted from its parent). In addition
insert takes time bounded by the number of points scanned past. Note that any
particular point p starts at the root and only moves downward (when evicted)
and there are only O(log n) levels. Hence during the execution of buildTree
both the total number of points evicted and the total number of points scanned
past is bounded by O(n log n).
⊓
⊔
Lemma 5. Each point is handled by buildTree in O (log n) amortized time.
Proof. By Lemma 4, the cost of all invocations of insert by algorithm buildTree
is O (n log n), which amortizes to O (log n) per point.
⊓
⊔
3.3

Hull Peeling

We begin the discussion of hull peeling by examining algorithm extractHull,
which takes a valid hull tree T , extracts from it the root hull chain T.hull, and
then returns it.
Algorithm 3.3: extractHull(T )

1
2
3

Input : T is a hull tree for a non-empty pointset P and H be the set of points
in T.hull.
Output: the hull h and T a hull tree for the point set P \ H
h = T.hull
delete(h, T )
return h

The correctness and cost of algorithm extractHull obviously depend on
delete. delete is called after a subchain has been cut out of the middle of
the root hull chain. This can be visualized if we imagine the root hull as a roof.
Further there is a left and a right “overhang” remaining after the middle of a roof
has caved in. The overhang might degenerate to just a sentinel point. Algorithm
delete itself also depends on other procedures which we discuss first.
3.3.1 below. We could just connect the two endpoints of the overhangs with
a straight line to repair the roof. However because of the curvature of the old
roof, some of the points in T.L or T.R might be above this new straight line. In
that case, these points need to move out of their subtrees and join in to form
the new root hull chain.
Therefore, we will need a Boolean function below(T, p, q) to that end. It
returns true if there exists a tangent of the root hull such that both p and q are
above it. A precondition of below(T, p, q) is that the root hull can rise above
the line through p and q only between p and q.
We also specify the Boolean function above(p, q, r) to be true if point r is
above the line passing through p and q. This is done with a standard constant
time test. Note that below is quite different than above. The functions pred
and succ operate on the corresponding hull chain in the obvious way.
Algorithm 3.4: below(T, pl , pr )

1
2
3
4
5
6
7
8
9

Input : T , a hull tree,
pl : the rightmost end in the left overhang,
pr : the leftmost point in the right overhang
Output: True iff every point of T.hull is below the line through pl and pr
if pl or pr is a sentinel then return false
if above(pred(T.r), T.r, Pl ) then
while ¬ above(T.l, succ(T.l), pr ) and ¬ above(pl , pr , T.l) do
T.l = succ(T.l)
return ¬ above(pl , pr , T.l)
else
while ¬ above(pred(T.r), T.r, pl ) and ¬ above(pl , pr , T.r) do
T.r = pred(T.r)
return ¬ above(pl , pr , T.r)

Lemma 6. Algorithm below runs in linear time. Further, if it returns false
either T.l or T.r is above the line through pl and pr .
Proof. Recall that one cursor may push the other cursor as it moves. Only one
cursor moves. If T.r is too far left to help decide, then T.l moves until it is above
the line or we find a tangent.
⊓
⊔
3.3.2 getBridge. Given two hull trees, where one precedes the other, algorithm getBridge scans the hull chains of the hull trees to find the bridge that
connects them.

Algorithm 3.5: getBridge(T.L, T.R)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Input : T.L: a left hull tree of some hull tree T ,
T.R: a right hull tree of T
Output: pl , pr : the left and right bridge points for T.L and T.R
if T.L = nil then pl = (−∞, −∞)
else pl = T.L.l
if T.R = nil or tail(T.L.hull).y > tail(T.R.hull).y then
pr = (+∞, −∞)
else pr = T.R.r
if above(T.L.l, T.R.r, succ(T.L.l)) then
T.L.l = succ(T.L.l)
(pl , pr ) = getBridge(T.L, T.R)
if above(T.L.l, T.R.r, pred(T.L.l)) then
T.L.l = pred(T.L.l)
(pl , pr ) = getBridge(T.L, T.R)
if above(T.L.l, T.R.r, succ(T.R.r)) then
T.R.r = succ(T.R.r)
(pl , pr ) = getBridge(T.L, T.R)
if above(T.L.l, T.R.r, pred(T.R.r)) then
T.R.r = pred(T.R.r)
(pl , pr ) = getBridge(T.L, T.R)
return (pl , pr )

Lemma 7. Given two valid hull trees T.L and T.R, getBridge correctly computes the bridge connecting T.L.hull and T.R.hull in time linear in the lengths
of those hulls.
Proof. The scan for the left bridge point in T.L is done using its left-to-right
cursor T.L.l, while the scan for the right bridge point in T.R is done using T.R’s
right-to-left cursor T.R.r. On completion, the two cursors will be pointing to
the bridge points. Since each vertex is scanned past at most once, the runtime
is O (|T.L.hull| + |T.R.hull|)). This completes the proof.
⊓
⊔
3.3.3 delete. The general idea of delete(C, T ) is that if C is a subchain
of T.hull then the procedure will return with the tree T being a valid hull tree
for the point set P \ H, where H is the set of points in C. The procedure will
be employed during the peeling process, and so C will initially be the entire
root hull. The root hull will have to be replaced by moving points up from the
subtrees. In fact the points moved up will be subchains of the root hulls of T.L
and T.R. Recursively, these subtrees will in turn need to repair their root hulls.
We do a case analysis below and find that the only procedure we will need is
delete.
Again we shall employ the analogy of a roof caving in, in the middle. The
rebuilding of the “roof” starts with identifying the endpoints of the remaining
left and right overhangs. These points will be the sentinels if the overhangs are

empty. The endpoints al and ar define a line segment, (al , ar ), which we shall
call the roof segment.
Before continuing, let us examine the dynamics of the points in the root
hull of a (sub)tree T during successive invocations of delete. Successive calls
might cause the roof segment (al , ar ) to get bigger. For successive roof segments,
the root hull of T is queried. There are two phases involved: before the root hull
intersects the roof segment, and thereafter. During the first phase, each new roof
segment is below the previous one (cf. Fig. 1 and Fig. 2). During the first phase,
the root hull is not changed but is queried by a series of roof segments (al , ar ).
In the second phase, it gives up its subchain from T.l to T.r to its parent (or
is extracted). Thereafter, for each new excision, T.l and T.r will move further
apart, until they become a sentinel. This is shown inductively on the depth of
the subtree.
In the first phase the cursors (T.l and T.r) start at the head and tail of
the list and move in response to below queries. Each cursor will move in one
direction at first and then, only once, change direction. This is because each
subsequent query has (al , ar ) moving apart on the parent’s convex chain. See
Fig. 1 and Fig. 2. Now we examine the algorithm more carefully.
ar

al
a′l

a′r

a′r

T.l

T.r

T.l

Fig. 1. Before al and ar move up.

T.r

a′l

Fig. 2. After al and ar have moved up.

The rebuilding process breaks into four cases depending on whether any
points from TL and TR are above the roof segment and hence will be involved
in the rebuilding.
Case 1. Neither subtree is needed to rebuild the roof.
This case, depicted in Fig. 3, is when the deletion of subchain C from T.hull
leaves a hull that already dominates all other points.
Case 2. Only the right subtree is needed to rebuild the roof.
This case, depicted in Fig. 4, is when T.hull no longer dominates the hull chain
in the right subtree. A second subcase is when the left root hull does extend
above the (al , ar ) segment but is still below the left tangent from the right root
hull. To maintain the hull tree invariants, a subchain of T.R.hull will have to be
extracted and moved up to become part of T.hull. In Case 2, only the vertices
of T.R.hull that will be moved up are scanned past twice, since points scanned
past in phase two are removed from the current hull.

Algorithm 3.6: delete(C, T )

1
2
3
4
5
6
7
8
9

10
11
12
13

14
15
16
17
18
19
20
21
22

Input : C, a chain of points to be deleted from T.hull,
T : a hull tree or points et P
Output: T : The updated hull tree for the point set P \ H
al = pred(head(C)); ar = succ(tail(C))
Use L = ¬ below(T.L, al , ar ); Use R = ¬ below(T.R, al , ar )
if Use L then (Ll , Lr ) = tangents(al , ar , T.L)
if Use R then (Rl , Rr ) = tangents(al , ar , T.R)
 Case 1: Neither subtree used to rebuild the roof
case ¬ Use L and ¬ Use R do nothing
 Case 2: Only the right subtree used to rebuild the roof
case Use R and (¬ Use L or above(ar , Ll , Rl )) do
CR = chain in T.R.hull from Rl to Rr , inclusive
Update T.hull with CR inserted between al and ar
delete(CR , T.R)
 Case 3: Only the left subtree used to rebuild the roof
case Use L and (¬ Use R or above(Rl , al , Lr )) do
CL = chain in T.L.hull from Ll to Lr , inclusive
Update T.hull with CL inserted between al and ar
delete(CL , T.L)
 Case 4: Both subtrees used to rebuild the roof
case Use L and Use R and above(al , Rl , Ll ) and above(Lr , ar , Rr ) do
(ql , qr ) = getBridge(T.L, T.R)
CL = chain in T.L.hull from Ll to ql , inclusive
CR = chain in T.R.hull from qr to Rr , inclusive
D = chain from concatenating CL to CR
Update T.hull with D inserted between al and ar
delete(CL , T.L)
delete(CR , T.R)
return T








ar

ar
al
al

Fig. 3. Case 1: al can connect to ar .

Fig. 4. Case 2: Right subtree involved in
rebuilding.

Case 3. Only the left subtree is needed to rebuild the roof.
This case, depicted in Fig. 5, is the converse of case 2, Again, a second subcase
is when the right root hull does extend above the (al , ar ) segment but is still

below the right tangent from the left root hull. As in the previous case, only the
vertices of T.L.hull that will be moved up are scanned twice.
Case 4. Both subtrees are needed to rebuild the roof.
In this case, we need to compute two subchains, one from T.l.hull and the other
from T.r.hull, which are then connected by a bridge to fix the roof.
ar

al

Fig. 5. Case 3: Only left subtree involved.

ar

al

Fig. 6. Case 4: Both subtrees involved.

Lemma 8. In Case 4, only the vertices of T.L.hull and T.R.hull that will be
moved up to join the roof are scanned twice.
Proof. Recall that after the call to getBridge, the two cursors T.L.l and T.R.r
are already pointing to the left and right bridge points.
The scan for the left tangent point visible to al and above the segment al ar
is done by walking T.L.l forward or backward. The decision of which direction
to walk can be done in constant time. If the walk toward T.L.r is chosen, then
all the points encountered will be encountered for the first time. However, if the
scan is backward toward the head of T.L.hull, then any point encountered is one
that will be moved up. A symmetrical argument applies on the right.
⊓
⊔
Theorem 1. Consider a sequence of calls to extractHull, starting with n
points, until all points have been extracted. The total time amortized over all
calls is O (n log n)
Proof. We assume that we start with a hull tree (built with buildTree). The
run time is dominated by cursor movement. Each procedure takes constant time
(and the number of calls is proportional to the number of chain movements) plus
the number of points a cursor has moved past. The above discussion shows that
each point is passed over a constant number of times before moving out a chain.
As with buildTree, this leads to our result.
⊓
⊔
3.4

Merge

Recall our discussion so far has only been for “northwest” hull trees, which we
now call TN W . We rotate the point set 90 degrees and recompute three times,

resulting in the four hull trees TN W , TN E , TSE , and TSW . We will use these to
construct the successive convex hulls by peeling. When the points are in general
position, the extreme points (topmost, bottommost, rightmost, and leftmost)
are on the convex hull. Note that some of these may coincide. Further, it is clear
that the chain that connects the leftmost point with the topmost is just the
northwest hull chain found at the root of TN W . The rest of the convex hull is
the root hull chains of the other trees.
Initially all the points are “unmarked”. When marked, a point is marked in all
four trees. We iteratively perform the following actions to construct each layer:
a) Retrieve and delete the root hull chain from each of the hull trees; b) Remove
the marked points from each chain; c) Mark the points remaining in each chain,
and d ) Concatenate the four chains to form the convex hull for this layer.
This process stops when all vertices have been marked, which is when all the
points have been deleted from all the trees. This correctness follows from above.
Lemma 9. Given a set S of n points and the four hull trees of P with the
four orientations of N W, N E, SE, and SE, the merge procedure executes in
O (n log n) time.
Proof. Note that the sum of the lengths of all the chains is O (n). So marking
points and removing them later all in all takes linear time. Recall that all the
calls to delete altogether take time O (n log n) time.
⊓
⊔

4

Conclusion

We have provided a new simple optimal algorithm for the convex layers problem. Detailed pseudocode, space and time complexity results are also given. The
pseudocode might appear detailed, but that is only because the approach is simple enough that we can deal with all cases explicitly. However, by using four sets
of hulls, we only need to work with monotone chains which simplifies our case
analyses and makes the correctness argument straightforward. The extension to
dynamic point sets remains an open problem.

References
1. Chan, T.: Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete & Computational Geometry 16(4), 361–368 (04 1996)
2. Chazelle, B.: On the convex layers of a planar set. IEEE Trans. Inf. Theor. 31(4),
509–517 (Sep 2006)
3. Green, P., Silverman, B.: Constructing the convex hull of a set of points in the plane.
Computer Journal 22, 262–266 (1979)
4. Nielsen, F.: Output-sensitive peeling of convex and maximal layers. Inf. Process.
Lett. 59(5), 255–259 (1996)
5. Overmars, M.H., van Leeuwen, J.: Maintenance of configurations in the plane. Journal of Computer and System Sciences 23(2), 166 – 204 (1981)
6. Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction.
Springer-Verlag, 3rd edn. (10 1990)

