Computing Maximal Layers Of Points in E f (n)
Indranil Banerjee, Dana Richards

arXiv:1508.02477v2 [cs.CG] 10 Nov 2015

George Mason University
Department Of Computer Science
Fairfax Virginia 22030, USA
{ibanerje,richards}@cs.gmu.edu

Abstract. In this paper we present a randomized algorithm for computing the collection of maximal layers for a point set in E k (k = f (n)). The input to our algorithm
is a point 
set P = {p1 , ..., pn } with pi ∈ E k . The proposed algorithm achieves a run2
2− 1 +logk (1+ k+1
) log n when P is a random order and a runtime of
time of O kn log k
O(k2 n3/2+(logk (k−1))/2 log n) for an arbitrary P . Both bounds hold in expectation. Additionally, the run time is bounded by O(kn2 ) in the worst case. This is the first non-trivial
algorithm whose run-time remains polynomial whenever f (n) is bounded by some polynomial in n while remaining sub-quadratic in n for constant k. The algorithm is implemented
using a new data-structure for storing and answering dominance queries over the set of
incomparable points.
Keywords: Maximal Layers, Random Order, Complexity

1

Introduction

The problem of finding the maximal layers of a set P = {p1 , ..., pn } of n points1 in [0, 1]k (where
k = f (n)) is analogous to the problem of finding the convex layers of P . Given P its first maximal
layer is defined to be the set M1 of points q ∈ P such that for any other p ∈ P , p 6≻ q. Here,
≻ is any ordering relation between two points. For example, we could define ≻ as follow: p ≻ q
if p[j] ≥ q[j] (where p[j] is the j th coordinate of p) for all j. The first maximal set M1 , which
we simply refer to as the maximal set of P , has been well studied [4,5,6]. The lth maximal layer
Ml is recursively defined as the first maximal layer of remainder of P upon removing from P
all the elements of layers from 1 to l − 1. Note that Ml could be empty. The maximal layers
problem is to identify all the non-empty maximal layers of P and report them. We shall denote
this problem as MaxLayers(P ).
Related Work. We only have a tight bound for MaxLayers(P ) when k ≤ 3, which is
Θ(n log n) [6,12]. However, we do not have any improved lower bound when k > 3. For fixed
k > 3 best known upper-bound is O(n(log n)k−1 ) [3]. Interestingly, the upper bound to find only
the first maximal set is O(n(log n)max(1,k−2) ). Both of these bounds hold in the worst-case. We
see that, for fixed k, these algorithms can be regarded as almost optimal, as they only have a
poly-logrithmic overhead over the theoretical lower bound. Conceptually, they implement multidimensional divide and conquer algorithms [7] on input P which introduces the poly-log factor
in their runtimes. The point set P is partitioned into subsets based on ordering of points in some
arbitrary dimension. Then the maximal sets are computed recursively and merged later.
Things get interesting if the number of dimensions is not bounded by a constant. When
k = Ω(log n), these poly-logarithmic upper-bounds above becomes quasi-polynomial (in n).
However, there is a trivial algorithm (which compares each point against the other, and keeps
track of the computed transitive relations) that requires in the worst case O(kn2 ) comparisons.
Although, for finding only the first maximal layer, [10] proposed a deterministic algorithm that
runs in O(n(3+ǫ)/2 ) when k = n. Where, O(nǫ ) is the complexity of multiplying two n × n
1

We have restricted the sampling set to [0, 1]k in order to simplify our analysis. the results hold for
any arbitrary compact subset of E k .

2

On Maximal Layers Problem

matrices. So we see that the algorithm runs in ω(n2 ) time. In a recent paper[11], authors show
that for determining whether there exists a pair (u, v), where u ∈ A and v ∈ B (A and B are
both sets of vector of size O(n)) such that u ≻ v, can be done in sub-quadratic time provided
k = O(log n).
Our Results. In this paper we propose a randomized algorithm for the MaxLayers(P ) problem. When
the point set P is also

 a random order the runtime of our algorithm is bounded
1
2
by O kn2− log k +logk (1+ k+1 ) log n in expectation. Otherwise, it is O(k 2 n3/2+(logk (k−1))/2 log n)

also in expectation. Additionally, it takes O(kn2 ) time in the worst case. This is the first nontrivial algorithm for which the following two conditions holds simultaneously: 1) The worst case
run time is polynomially bounded (in n) as long as k is bounded by some polynomial in n.
2) Whenever k is a constant the run time of the proposed algorithm is sub-quadratic in n (in
expectation).

2

Preliminaries

We denote P = {p1 , ..., pn } as the input set of n points in E k . The j th coordinate of a point p
is denoted as p[j]. For any points p, q ∈ P , we define an ordering relation ≻, such that p ≻ q
if p[j] op q[j] ∀j ∈ [1...k]. Where, op is a place holder for ≥ or ≤. Consequently, there are 2k
different ordering relations ≻ and for each such an ordering there is a unique set of maximal layers
(of P ). Without loss of generality, we assume that op is ≥ for all j, in this paper. Henceforth
we will simply use ≥ in place of op. We will use the notation S ≻ p, where S is a set of
incomparable elements, to denote that ∃q ∈ S such that q ≻ p. If S ≻ p we say that S is “above”
p. Furthermore, if p  q then either p = q or p ≻ q.
Clearly, (P, ≻) defines a partial order. We shall simply use P to denote this poset when the
context is clear. If p ≻ q then we say that p precedes (or dominates) q in the partial order and
that they are comparable. We say that p and q are incomparable (denoted by p k q) if p 6≻ q and
q 6≻ p. If p and q belong to the same maximal layer then p k q. Let the height h of P be defined
as the number of non-empty maximal layers of P . We also define the width w of P as the size
of the largest subset of P of mutually incomparable elements. Note, that the maximum size of
any layer is ≤ w.
Let O : E k × E k → {0, 1}k , such that O(p, q)[j] = 1 if p[j] < q[j] and 0 otherwise. This
definition, which might seem inverted, will make sense when we discuss it in the context of our
data structures. We call O the orthant function as it computes the orthant with origin p in which
q resides. Henceforth, the maximal layers will simply be referred to as layers. Let T be a linear
ordering of the points in P such that for any p, q ∈ P , if p ≻ q then p precedes q in T , that is, a
liner-extension preserves the precedence relations between the elements of P . Let |S| denote the
size of the set S. We are now ready to state the MaxLayers(P ) problem formally:
Definition 1 (MaxLayers(P )). Given a point set P along with an ordering relation defined
above, label each point in P with rank of the maximal layer it belongs to.
In our analysis we shall use the typical RAM model, where operation of the form p[j] ≥ q[j]?
takes constant time. In our analysis we shall first assume that the point set P forms a random
order. Then we will extend the result for an arbitrary set of points. Below we define random
orders formally according to its definition in [1].
Definition 2. We pick a set of n points uniformly at random from [0, 1]k . Then the partial
order generated by these points is a random order.
This is equivalent to saying that (P, ≻) is the intersection of k linear orders T1 × ... × Tk
where the k-tuple (T1 , ..., Tk ) is chosen uniformly at random from (n!)k such tuples. Here, each
Tj is a linear ordering (permutation) of {1, 2, ..., n}. Whenever we present our run-time results
in terms of w or (and) h it is assumed that both are upper bounded by n, the number of points
in P . To simplify our analysis we ignore the expected values of w and h, which could only have
made our results stronger (for example, see [1,2]).

Maximal Layers Problem

3

3

The Iterative Algorithm

We shall use MaxPartition(P ) as the main procedure for solving an instance of MaxLayers(P ). First we will describe a simpler algorithm and analyze it for a random order P . Then
we extend it for an arbitrary set of points.
3.1

Data Structures

In this section we introduce the framework on which our algorithm is based. Let B be a selfbalancing binary search tree (for example B could be realized as a red-black tree). Let B(i)
be the ith node in the in-order of B. Each node of B stores three pointers. One for each of its
children (null in place of an empty child) and another pointer which points to an auxiliary data
structure. If X is a node in B then left and right children of X are denoted as l(X) and r(X)
respectively. We also denote by L(X) the auxiliary data structure associate with X. When the
context is clear, we shall simply use L in place of L(X).
We also let L be a placeholder for any data structure that can be used to store the set of
points from a single layer of P . For example, L could be realized as a linked list. Additionally,
L must support Insert(L, p) and Above(L, p). The Above(L, p) operation takes a query point
p, and answers the query L ≻ p? . The Insert(L, p) operation inserts p into L, which assumes p
is incomparable to the elements in L. So, we must ensure that L is the correct layer for p before
calling Insert(L, p).
We observe that the layers of P are themselves linearly ordered by their ranks from 1 to
h. We can thus use B to store the layers in sorted order, where each node B(i) would store
the corresponding layer Mi (using L(B(i))). We endow B with Insert(B, p) and Search(B, p)
(we do not need deletion) operations. The Insert(B, p) procedure first calls the Search(B, p)
procedure to identify which node B(i) of B the new point p should belong and then calls
Insert(L(B(i)), p). If p does not belong to any layer currently in B then we create a new node
in B. The Search(B, p) procedure works as follows: we can think of B as a normal binary search
tree, where the usual comparison operator ≥ has been replaced by the Above(L, p) procedure.
Furthermore, the procedure can only identify whether L ≻ p or L 6≻ p. This is exactly equivalent
to the situation where we have replaced the comparison operator ≥ with >. So we must determine
two successive nodes B(i) and B(i + 1) such that L(B(i)) ≻ p and L(B(i + 1)) 6≻ p. If such a
pair of nodes does not exist then we return a null node.
3.2

MaxPartition(P )

We begin by first computing a linear extension T of P . We initialize B as an empty tree. We
iteratively pick points from P in increasing order of their ranks in T and call Insert(B, p),
where p is the current point to be processed. Insert(B, p) subsequently calls Search(B, p). We
have two possibilities:
case 1: Search(B, p) returns a non-empty node B(i). We then call Insert(L(B(i), p).
case 2: Search(B, p) returns a null node. Then we create the node B(m + 1) in B, where m
is the number of nodes currently in B. We first initialize B(m+1) and then call Insert(L(B(m+
1), p) on it. We note that, when we create a new node in B it must always be the right-most node
in in-order of B. This follows from the order in which we process the points. Since p succeeds a
processed point q in the linear extension T , hence p 6≻ q. Thus, if p does not belong to any of
nodes currently in B then it must be the case that p is below all layers in B.
MaxPartition(P ) terminates after all points have been processed. At termination L(B(i))
stores all of the points in Mi for 1 ≤ i ≤ h. We make a couple of observations here. 1) When a
point is inserted into a node B(i) it will never be displaced from it by any point arriving after it.
2) Since, nodes are always added as the right-most node in B, for Search(B, p) to be efficient,
B must support self-rebalancing.
If we assume that Above(L, p) and Insert(L, p) to work correctly, at once we see that
Search(B, p) and Insert(B, p) are also correct. Hence, each point is correctly assigned to the
layer it belongs to.

4

3.3

On Maximal Layers Problem

Runtime Analysis

Let Above(L, p) take ta (|L|) time. As mentioned in section 2, |L| ≤ w for any layer in B. Hence,
ta (w) is an upper bound on the runtime of Above(L, p). Similarly, we bound the runtime of
Insert(L, p) with ti (w). Let p be the next point to be processed. At the time B will have at
most h nodes. In order to process p the Insert(B, p) will be invoked, which in turn calls the
Search(B, p) as discussed above. But the Search(B, p) will employ a normal binary search
on B with the exception that at each node of B it invokes the Above(L, p) instead of doing a
standard comparison. Since, B is self-balancing the height of B is bounded by O(log h). Hence,
number of calls to Above(L, p) is also bounded by O(log h), each of which takes ta (w) time.
Also, for each point p, Insert(L, p) is called only once. We also assume initializing a node in B
takes constant time. So, processing of p takes O(ta (w) log h + ti (w)) and this holds for any point.
Lemma 1. We can compute a linear extension T of P in O(n log n + kn) time in the worst
case.
Proof. We shall compute T as follows: Let µ(p) = max1≤j≤k p[j]. Then sorting the points in
decreasing order of µ(p) will give us T . It is trivial to see that T is a linear extension of P . This
takes O(n log n + kn) in the worst case.
The reason for computing T in this way will be clear when we get to the analysis of our algorithm. Later we shall see that the time bounds for Above(L, p) and Insert(L, p) will dominate
the time it takes to compute T . So we shall ignore this term in our run-time analysis. The next
theorem trivially follows from the discussion above.
Theorem 1. The procedure MaxPartition(P ) takes O(n(ta (w) log h + ti (w))) time and upon
termination outputs a data structure consisting of the maximal layers of P in sorted order.

4

Realization of L using Half-Space Trees

In this section we introduce a new data structure for implementing L. We shall refer to it as
Half-Space Tree (HST).
The function O(p, q) computes which orthant q belongs to with respect to p as the origin.
Clearly, there are 2k such orthants, each having a unique label in {0, 1}k . Let Hj (p) be a half
space defined as: Hj (p) = {q ∈ [0, 1]k | O(p, q) = {0, 1}j−1 0{0, 1}k−j } passing through origin p
whose normal is parallel to dimension j. Here, {0, 1}j−1 0{0, 1}k−j represents a 0-1 vector for
which the j th component is 0. We shall use the notation hj (p) to denote the extremum orthant
of Hj (p) (w.r.t ≻), that is, hj (p) = 1j−1 01k−j . There are k such half spaces. An orthant whose
label contains m 1’s lies in the intersection of some k − m such half spaces.

Lemma 2. If p, q ∈ P and p k q then O(p, q) ∈ {0, 1}k \ {0k , 1k }. That is, q can only belong to
orthants which lie in the intersection of at most k − 1 half spaces.
Proof. Trivially follows from definitions.
Corollary 1. The above lemma holds if p and q belongs to the same layer. However, the converse
of this statement is not true.
4.1

Half-Space Tree

We define a k-dimensional HST recursively as follows:
Definition 3 (HST). 1. A singleton node (root) storing a point p.
2. A root has a number of non-empty children nodes (up to k) each of which is a HST.
3. If node q is the j th child of node p then hj (p)  O(p, q).
An HST stores points from a single layer. So Corollary 1 tells us that for any node p and a
new point q at most k − 1 of the children nodes satisfy hj (p)  O(p, q). Hence, q can be inserted
into any one out of these children nodes. Henceforth, we will also use w (the width of (P, ≻)) to
bound the number of points currently stored inside L.

Maximal Layers Problem

5

Above(L, p) Let us assume that L is realized by an HST. The Above(L, p) works as follows:
First we compute O(r, p). Here, r is the root node. If O(r, p) = 0k then we return L ≻ p.
Otherwise we call Above(j(L), p) recursively on each non-empty child node j of root r, such
that hj (r)  O(r, p). When all calls reach some leaf node, we stop and return L 6≻ p.
of correctness. case 1:(L ≻ p) Let q be some point in L such that q ≻ p, prior to calling
Above(L, p). Before reaching the node q, if we find some other node q ′ ≻ p then we are done.
So we assume this is not the case. We claim that p will be compared with q. We show this as
follows: Let the length of path from root r to q be i + 1. Let u0 , ..., ui be the sequence of nodes
in this path (here u0 = r and ui = q). Since, q ≻ p, O(um , q)  O(um , p) for all 0 ≤ m < i. But,
um is a predecessor node in the path from r to q, hence hjm (um )  O(um , q) where um+1 is the
th
jm
child of um . Which implies hjm (um )  O(um , p) (from transitivity of ) for 0 ≤ m < i. Thus
we will traverse this path at some point during our search.
case 2:(L 6≻ p) Follows trivially from the description of Above(L, p).
Insert(L, p) Insert(L, p) is called with the assumption that L 6≻ p. If the root is empty then
we make p as the root and stop. Otherwise, we pick one element uniformly at random from the
set Sr = {j ∈ {1, ..., k} | hj (r)  O(r, p)} and recursively call Insert(j(L), p).
of correctness. It is easy to verify that insert procedure maintains the properties of HST given
in definition 2.
Although the insert procedure is itself quite simple, it is important that we understand the
random choices it makes before moving further. These observation will be crucial to our analysis
later. Let the current height of L be hL . By L∗ we denote the complete HST of height hL , clearly
L∗ has k hl nodes. We color edges of L∗ red if both of the nodes it is incident to are present in
L, otherwise we color it blue. Unlike Above, we can imagine that the Insert procedure works
with L∗ instead of L. Upon reaching a node r in L∗ the procedure samples uniformly at random
from the set Sr as above. This set may contain edges of either color. If a blue edge have been
sampled then we stop and insert p into the empty node incident to the blue edge in L. So we
see that, despite not being in L, the nodes incident to blue edges effect the sampling probability
equally.
4.2

Runtime Analysis

Here we compute ta (w) and ti (w) in expectation over the random order P and the internal
randomness of the Insert(L, p) procedure. From the discussion in section 4.1 we clearly see that
ti (w) = O(ta (w)). So it suffices to upper bound ta (w) in expectation. Furthermore, we only need
to consider the case when Above(L, p) returns L 6≻ p as the other case would take fewer number
of comparisons. Let this time be u(w). We divide our derivations to compute u(w) into two main
steps:
i. Compute the expected number of nodes at depth d of L having w nodes.
ii. Use that to put an upper bound on the number of nodes visited during a call to Above(L, p)
(when L 6≻ p).
We choose to process points according to T as detailed earlier. We denote this ordering by
the ordered sequence (p1 , ..., pn ).
Lemma 3. For any two points p, q where p precedes q in T we have the probability that p[j] > q[j]
1
1 k−2
is η1 (k) = 1 − 12 k−1
k+1 . Additionally, if p and q are incomparable then it is η2 (k) = 1 − k − 2 k+2 .
Proof. See appendix.
Theorem 2. After w insertions the expected number of nodes at depth d in L is given by:
!
d
X
(1 − k1i )w−1
d
k 1−
Qd
1
j=1,j6=i (1 − ki−j )
i=1

6

On Maximal Layers Problem

Proof. Let Xw,d be the number of nodes at depth d of L after w insertions. Due to the second
assertion of Lemma 3 we know that any new point to be inserted can belong to any of the k
half-spaces with probability η2 (k), which is constant over the half-spaces. The insert procedure
selects one of these candidate half-spaces uniformly at random. Thus it follows from symmetry
that a particular half-space will be chosen for insertion with probability k1 . If the subtree is
non-empty then we do these recursively. We define an indicator random variable for the event
that the tth insertion adds a node at depth d as It,d . Then,
Xw,d =

w
X

It,d

t=1

Taking expectation on both side we get,
E[Xw,d ] =

w
X

Pr[It,d ]

t=1

X

Trivially, E[Xw,0 ] = 1 for t > 0. When d = 1 and t ≥ 2 then Pr [It,1 ] = 1 − t−1,1
. This is
k
because there are Xt−1,1 nodes at depth 1 (nodes directly connected to the root) hence there are
k − Xt−1,1 empty slots for the node to get inserted at depth 1, otherwise it will be recursively
inserted to some deeper node. Hence we have,
E[Xw,1 ] =

w 
X
t=2

1−

Xt−1,1
k



For d = 2, we can similarly argue that the probability of insertion at depth 2 for some t ≥ 3
is equal to probability of reaching a node at depth
 of being inserted at
 the probability
 1 times
Xt−1,2
Xt−1,1
1 − kXt−1,1 . Hence,
depth 2. It is not difficult to see that this equals:
k
E[Xw,2 ] =


w 
X
Xt−1,1
t=3

k

Xt−1,2
1−
kXt−1,1



Proceeding in this way we see that,
E[Xw,d ] =

w 
X
E[Xt−1,d−1 ]
t=1

k d−1

E[Xt−1,d ]
−
kd



Here we again take expectation on both sides and simplify the expression so that the sum starts
from t = 1 since the terms E[Xt,d ] = 0 when t ≤ d.
Let a(w, d) = E[Xw,d ], we can then simplify the above equation to get the following recurrence,


a(w − 1, d − 1)
1
a(w, d) =
+ 1 − d a(w − 1, d)
k d−1
k
with a(w, d) = 0 for w ≤ d. The solution to this can be
by choosing a ordinary generating
Pfound
∞
function Gd (z) with parameter d, such that Gd (z) = t=0 a(t, d)z t . The solution [see appendix]
completes the proof of the theorem.
Before moving on to the main theorem we need another lemma:
Lemma 4. If B = (b0 , b1 , ..., bn ) is a sequence such that br ≥ br+1 ≥ ... ≥ bn , then the sum
P
P
mr+1
where m < 1.
S = ni=0 bi mi ≤ ri=0 bi mi + br+1
(1−m)
Proof. See appendix.

Corollary 2. If m = 1 −

1 k−1
2 k+1

and k ≥ 4 then , S ≤

Pr

i=0 bi m

i

+ 37 br+1 mr .

Maximal Layers Problem

7

Theorem
3. Expected number
of nodes visited during an unsuccessful search u(w) is bounded


2
1
by O w1− log k +logk (1+ k+1 ) .

Proof. Before proving this we make the following observation. If for any d = d0 , the sequence
a(w, d) becomes decreasing, that is, a(w, d0 ) ≥ a(w, d0 − 1) and a(w, d0 ) > a(w, d0 + 1), then
afterwards it will stay decreasing. This is clear from the fact that a(w, d) represents the expected
number of nodes at depth d after w insertions. So the sequence a(w, d) is unimodal since a(w, 0) ≤
a(w, 1) trivially for w ≥ 2. Let d0 be the value that maximizes a(w, d).
Let us compute the probability of visiting a node at depth d during a call to Above when the
query point is not below L. Let q be the current node being checked and p be the query point.
According to Lemma 3 the probability Pr[p ∈ Hj (q)] is same for any j and is not dependent
on the rank of q in T . Hence it is also not dependent on the depth of q in L. Furthermore, this
k−1
, again from Lemma 3.
probability is η1 = 1 − 21 k+1
Thus the probability of visiting a node at depth d is the result of d independent moves each
having probability η1 , hence it is η1d . Now we can find the expression for the expected number
of nodes visited:
u(w) =

w−1
X

η1d a(w, d)

d=0

≤

d0
X
d=0

7
η1d a(w, d) + η1d0 a(w, d0 + 1)
3
(1)

Here we use Theorem 2, Lemma 4 and its corollary and the fact that the sequence a(w, d) is
unimodal; to bound u(w). Also note that a(w, d) ≤ k d . Now we need to upper bound d0 . With
some tedious algebra [see appendix] we get, d0 ≤ logk w + 2. Again, after some more algebra [see
appendix] we finally get,

This proves Theorem 3.



2
1
u(w) ≤ O w1− log k +logk (1+ k+1 )

(2)



1
2
Corollary 3. The algorithm runs in O kn2− log k +logk (1+ k+1 ) log n in expectation.

Proof. From Theorem 1 and the first paragraph of Section 4.2 we see that the runtime of the
algorithm is O(knu(w) log h). Since computing O(p, q) between pairs of vectors takes O(k) time.
Using the upper-bound of u(w) and the fact that w, h ≤ n we get the runtime as claimed above.

5

Extension to Arbitrary P

The previous algorithm would still be correct if P is not a random order. However the expected
runtime will no longer hold. In order make our previous analysis work for any set of points we
modify the way we store the layers. In this new setting layers are still arranged using a balanced
binary B, exactly as before. However, each layer is now stored using a list of HSTs instead of
just a single one. Let us call this data structure List-HST. We extend the Above and Insert
procedure for HST in a obvious way.
List-HST starts with an empty list. Attached to a List-HST is another list R in which
newly arrived points are kept temporarily before they are ready to be inserted
in the List-HST.
√
Initially
this
list
R
is
also
empty.
We
take
the
maximum
size
of
R
as
w.
As
long
as R has less
√
than w points we keep adding to it. Once R has been filled, we create an HST from the points
in R and remove these points from R. This becomes the first HST in the list. We repeat these
steps again when R is full. We describe the modified List-HST-Above and List-HST-Insert
below.

8

On Maximal Layers Problem

List-HST-Insert(p) If R is not yet full then we just add p to R. Otherwise we create HST
from points in P ′ = R ∪ p. We randomly permute elements in P ′ and pick the first element in
this ordering as the root. We then build the HST iteratively by picking elements in this order.
Next we prove a lemma similar to Lemma 3.
Lemma 5. Assume that an HST is build by inserting points in a random order. Let X represents
a point which is already inserted and Y a new point being compared to X. Then Y belongs to
any of the children subtree of X with equal probability.
Proof. Since the insertion order is random, X and Y are both random variables. We compute the
probability Pr[X[i] > Y [i]] for some i. Now for some arbitrary pair of points {p, q} the probability
that p precedes q in the ordering is 1/2. If X, Y ∈ {p, q} then, Pr[X[i] > Y [i]|X, Y ∈ {p, q}] =
(Pr[X[i] > Y [i]|X = p, Y = q] + Pr[X[i] > Y [i]|X = q, Y = p])/2. Pr[p[i] > q[i]]is either 0 or 1
since the points p and q themselves are not random. Hence, Pr[X[i] > Y [i]|X, Y ∈ {p, q}] = 1/2
for any pair {p, q}, which proves the claim above.
Using
the above lemma and techniques used
√
√ to prove Theorem 3 we can show that d0 ≤
logk w + 2. Hence, building an
HST
takes
O(
w logk w) time in expectation and O(w) in worst
√
case. Since, there can only be n such steps where we build an HST and each takes O(n) (since
w ≤ n) time hence the insert operation on List-HST adds O(n3/2 ) to the overall running time
of our algorithm. This is insignificant compared to the total time.
List-HST-Above(p) For each HST L in the list we call Above(L, p). If none of these calls
find a point above p then we check the remaining points in R. However, since p is not random
we cant compute the probability η1 as we did before. However, we can upper bound the fraction
of subtrees that are visited from a node. We see that a point p can visit at most k − 1 subtrees
of a node q otherwise we can conclude that q ≻ p. The List-HST-Insert procedure creates the
j th subtree of q with equal probability for all j. Hence, during the search step the point p will
visit a non-empty subtree of q is with probability ≤ (k − 1)/k. This value can be substituted as
√ log (k−1)
). Since there are
an upper√bound for η1 in Equation 1, which leads to u(w) ≤ O(k w k
to search a
at most w HSTs in a layers, it takes O(kw1/2+(log k (k−1))/2 ) time in expectation
√
list of HSTs. We ignore the time it takes to check the set R, which is O(k w). Hence the total
runtime is bounded by O(k 2 n3/2+(logk (k−1))/2 log n) in expectation.
5.1

A Summary of Results

We summarize the main results as follows:
i. k is a constant. From Corollary 3 we can easily verify that the algorithm has a runtime of
O(n2−δ(k) ) where δ(k) > 0. This remains true even when P is not a random order.
ii. k is some function of n We let k = f (n). For any k the runtime of our algorithm is bounded
by O(kn2 ) in the worst case. This bound does not hold for the divide-and-conquer algorithm
in [3]. Also, The proposed algorithm never admits a quasi-polynomial runtime unlike any of
the previously proposed non-trivial algorithms.
Concluding Remarks
In this paper we proposed a randomized algorithm for the MaxLayers(P ) problem. Unlike previous authors we also consider the case when k is not a constant; this is often the case for many
real-world data sets whose tuple dimensions are not insignificant with
to its set size. In
 respect
1
2
2− log
+logk (1+ k+1
) log n
k
this setting we show that the expected runtime of our algorithm is O kn
when P is a random order. For any arbitrary set of points in E k it exhibits a runtime of
O(k 2 n3/2+(logk (k−1))/2 log n) in expectation. It remains to be seen if there exists a determinist
algorithm that runs in o(kn2 ) for this problem. As a future work it would be interesting to know
whether HST can be used for the unordered convex layers problem in higher dimensions. We
know that unlike the maximal layers problem this problem is not decomposable [8]. So it would
be interesting to know within our iterative framework whether we can extend HST to store the
convex layers also.

Maximal Layers Problem

9

References
1. Winkler, P., Random Orders, Order, 1-4, 317-331 (1985)
2. Brightwell, G., Random k-Dimensional Orders: Width and Number of Linear Extensions, Order , 9,
333-342 , (1992)
3. Jensen M. T., Reducing the Run-Time Complexity of Multiobjective EAs: The NSGA-II and Other
Algorithms, IEEE TEC, 7-5, 503-515 (2003)
4. Kung H. T., Luccio F., Preparata F. P., On Finding the maxima of a Set of Vectors, Journal of ACM,
22-4, 469-476 (1975)
5. Bentley J. L., Kung H. T., Schkolnick M., Thompson C. D., On the Average Number of Maxima in
a Set of Vectors and Applications, Journal of ACM, 25-4, 536-543 (1978)
6. Yao F. F. On Finding the maximal elements in a set of plane vectors, Comp. Sci. Dept. Rep, U. of
Illinois at Urbana-Champaign, Urbana, Ill., 1974
7. Bentley J. L., Multidimensional Divide-and-conquer, Commun. ACM, 23-4, 214-229 (1980)
8. Preparata P., Shamos M.: Computational Geometry: An Introduction. Texts and Monographs in
Computer Science (1985)
9. Overmars M. H.: The Design of Dynamic Data Structures. LNCS 156, New York Tokyo (1983)
10. Matoušek, J., Computing dominance in E n , Information Processing Letters, 38, 277-278 (1991)
11. Impagliazzo R.,Lovett S., Paturi R., Schneider S., 0-1 Integer Linear Programming with a Linear
Number of Constraints, eprint arXiv:1401.5512 (2014)
12. Nielsen F., Output-sensitive peeling of convex and maximal layers, Information Processing Letters,
59, 255 - 259 (1996)

Appendix
Proof of Lemma 3
Proof. Recall that T is a linear extension of P . Since p precedes q in T , µ(p) > µ(q). Hence,
′
∃ j ∈ {1, ..., k} such that p[j ′ ] > q[j ′ ]. Let j ′ = argmax1≤j≤k p[j]. We compute the probability
′
′
Pr[p[j] > q[j] | µ(p) > µ(q)] in two parts over the disjoint sets {j = j } and {j 6= j }:
′

′

′

′

Pr[p[j] > q[j] | µ(p) > µ(q)] = Pr[p[j] > q[j] | j = j , µ(p) > µ(q)] Pr[j = j ]
+ Pr[p[j] > q[j] | j 6= j , µ(p) > µ(q)] Pr[j 6= j ]



1
1
1 µ(q)
1−
=1 + 1−
k
2 µ(p)
k

(3)

Since,
(µ(p) − µ(q))µ(q) +
Pr[p[j] > q[j] | j =
6 j , µ(p) > µ(q)] =
µ(p)µ(q)
′

µ(q)2
2

=1−

1 µ(q)
2 µ(p)

This follows from the fact that p[j] and q[j] are independent random variables uniformly dis′
tributed over [0, µ(p)] and [0, µ(q)] (given µ(p) > µ(q)) respectively. In the set{j = j } clearly

′

µ(q)
p[j] > q[j]. However, in the set {j 6= j } the probability that p[j] > q[j] is 1 − 21 µ(p)
. We
note that µ(p), µ(q) are themselves random variables. More importantly they are i.i.d random
variables having the following distribution:

Pr[µ(p) < t] = tk
on the interval [0, 1]. This follows from how points in P are constructed. We take the expectation
of both side of Equation 3.1 over the event space generated by µ(p), µ(q) on the set {µ(p) > µ(q)}:



1
µ(q)
1
| µ(p) > µ(q) 1 −
Pr[p[j] > q[j] | µ(p) > µ(q)] = 1 − E
2
µ(p)
k





1
1 k−1
k
1
1−
=1−
=1−
2 k+1
k
2 k+1

10

On Maximal Layers Problem

Now, let us compute, E

h

µ(q)
µ(p)

tribution function of µ(p) is,

i
| µ(p) > µ(q) . Recall that µ(p) = max1≤i≤k p[j]. So the dis

F [µ(p)] = Pr[µ(p) < t] = Pr 

^

1≤i≤k



Y

p[i] < t =

Pr[p[i] < t] = tk

1≤i≤k

Where the second equality comes from that fact that each component of p are independent and
identically distributed on [0, 1] with uniform probability. Hence,
 Z

µ(q)
µ(q)
| µ(p) > µ(q) =
dF [µ(p)]dF [µ(q)]
E
µ(p)
µ(p)>µ(q) µ(p)
Z 1 Z µ(p)
k2
µ(p)k−2 µ(q)k dµ(p)dµ(p)
=
Pr[µ(p) > µ(q)] 0 0
k
=
k+1
A similar argument can be used to prove the second claim.
Solving a(w, d)
To simplify our calculations we modify the recurrence slightly: With a(w, d) = k d b(w, d), the
recurrence equation becomes,
1
1
b(w − 1, d − 1) + (1 − d )b(w − 1, d)
kd
k
P∞
Let, Gd (z) = w=0 b(w, d)z w . We note that b(w, d) = 0 when w ≤ d. Then we have,
b(w, d) =

z
1
Gd−1 (z) + z(1 − d )Gd (z)
kd
k
z
Gd−1 (z)
= d
k (1 − (1 − k1d )z)

Gd (z) =

...

= Qd

i=1

But, G0 (z) =

P∞

w=0 b(w, 0)z

w

=

P∞

w=1

zd
k i (1 − (1 −

zw =

z
1−z

G0 (z)

1
ki )z)

as b(w, 0) = a(w, 0) = 1 when w ≥ 1. Hence,

b(w, d) = k −d(d+1)/2 [z w−d−1]Gd (z)
= k −d(d+1)/2 [z w−d−1]

1
(1 − z)

Qd

i=1

(1 − (1 − k −i )z)

(4)

Where the notation [z i ]p(z) means the coefficient of z i in the polynomial p(z) as usual. Using
partial fractions: Let,
d

1
(1 − z)

Qd

i=1

(1 − (1 − k −1 )z)

≡

For which we get the following solution,

X
β0
βi
+
1 − z i=1 (1 − (1 − k −i )z)

β0 = k d(d+1)/2
k d(d+1)/2 (1 − k −i )d
βi = Q d
j−i )
j6=i,j≥1 (1 − k

Substituting these in Equation 4 above we get, b(w, d) = 1 −
us the desired result for a(w, d).

Pd

i=1

Qd

(1−k−i )w−1
,
(1−kj−i )

j=1,j6=i

which gives

Maximal Layers Problem

Proof of Lemma 4
Pn
We have, S = i=0 bi mi , where br ≥ br+1 ≥ ... ≥ bn . But then,
S=

r
X

b i mi +

i=0

=

r
X

n
X

i=r+1

b i mi +

i=0

b i mi ≤
r+1

br+1 m
1−m

r
X

b i mi +

i=0

n
X

11

br+1 mi

i=r+1

Computing d0
We shall denote d0 as d0 (w, k) as it is a function of both w and k. Hence, d0 (w, k) maximizes
a(w, d) as d varies from 0 to w − 1. Since we are interested in an upper bound on d0 (w, k),
we may think of d being fixed and we vary w from 0 to ∞2 . If we then lower bound w, when
a(w, d) maximum, we will be able get a corresponding upper bound for d0 (w, k). This makes our
analysis simpler as the number of terms in the expression for a(w, d) is fixed for a fixed d.
Let,
a′ (w, d) = a(w, d − 1) − a(w, d)
=k
Letting αi = 1 −

d−1

1
ki

1−

d−1
X
i=1

we get,

1 w−1
ki )

(1 −

Qd−1

j=1,j6=i

(1 −

1
ki−j

)

!

a′ (w, d) = −k d−1 (k − 1) + k d−1

−k

d

1−

d
X
i=1

Qd

(1 −

j=1,j6=i

1 w−1
ki )

(1 −

1
ki−j

)

!

d
X
αi w−1 (k − αi−d )
Qd
j=1,j6=i αi−j
i=1

Since we wish to compute d0 (w, k) or at least get an upper bound, we assume that a′ (w, d) < 0.
Hence,

Since,

Qd

j=1,j6=i

Let A = k

d
X
αi w−1 (k − αi−d )
<k−1
Qd
i=1
j=1,j6=i αi−j

Qd−i
j=1 (1
j=1 αi−j
αi w−1
i=1 P (i−1) Qd−i 1−kj and
j=1

αi−j =
Pd

Qi−1

Qd−i
Qi−1
− k j ) = P (i−1) j=1 (1 − k j ), where, P (i) = j=1 αi−j .
Pd
αi w−1 αi−d
B =
i=1 P (i−1) Qd−i 1−kj . Then according to our
j=1

assumption, A + B < k − 1.
However, writing out the terms in the expression for A yields:

A=k
=k
≥k

αw−1
αw−1
αw−1
d−1
d−2
d
−
+
− ...
P (d − 1) (k − 1)P (d − 2) (k − 1)(k 2 − 1)P (d − 3)
!
w−1
α
αw−1
1
d−1
d
−
+ o( 2 ) − ...
P (d − 1) (k − 1)P (d − 2)
k
!
αw−1
αw−1
d−1
d
−
P (d − 1) (k − 1)P (d − 2)
αw−1

!

1
It is not difficult to see that (k−1)(k2d−2
−1)P (d−3) − ... ≤ o( k2 ). Since, P (i) < P (j) when i > j and
w−1
αi
decreases as i → 0. Similarly, we can show that,

B≥−
2

αw−1
d−1
P (d − 2)

actually from d + 1 as terms below it are 0, but this does not affect our analysis

12

On Maximal Layers Problem

Thus we get,
w−1

αd−1
αw−1
d
k
−
P (d − 1) P (d − 2)


1+

k
k−1



<k−1

Since we want to get an upper bound for d0 (w, k) we assume that w is sufficiently large. More
precisely, we let w ≥ ck d−1 + 1 where 0 < c < 1. But then,
αw−1
d−1


= 1−
≤ e−c

1

k d−1
3
≈
5

w−1


≤ 1−

1
k d−1

ckd−1

Here we take c = 12 . Putting this value for αw−1
d−1 in the main equation and dividing both sides
by k we get,
αw−1
2k − 1
1 3
d
<1− +
P (d − 1)
k 5 k(k − 1)P (d − 1)
Since P (d − 1) < P (d − 2). But,


 

1
1
1
1−
1 − 2 ... 1 − d−1
k
k
k
1
1
1
1
1
1
= 1 − − 2 + 5 + 7 + ... ≥ 1 − − 2
k
k
k
k
k k

P (d − 1) > P (d) =

And P (d − 1) < 1 − k1 . Substituting these upper and lower bound of P (d − 1) to LHS and RHS
of the expression respectively we get,
k

αw−1
(2k − 1)k
1 3
γ(k)
d
<1− +
≤1+
k−1
k
5 (k − 1)(k 2 − k − 1)
k

Where 0 < γ(k) < 1 for k ≥ 4. So we have,


w


w
1
1
1
γ(k)
w−1
1− d < 1− d
1−
<1− 2
< αd
< 1+
k
k
k
k
k
So we get, d < logk w + 2. This is the upper bound on d0 (w, k) that we have sought for.
Derivation of Equation 3 in Theorem 3
We know d0 ≤ β + 3. Where, β = ⌊logk w⌋. Hence (for k ≥ 4),
u(w) =

w−1
X

η1d a(w, d)

d=0

≤
≤

d0
X

d=0

β
X

d=0

7
η1d a(w, d) + η1d0 a(w, d0 + 1)
3
7
η1d k d + η1 β+1 (a(w, β + 1) + a(w, β + 2) + a(w, β + 3)) + η1β+3 a(w, β + 4)
3

Here we observe that, a(w, β + i) ≤ w for 1 ≥ i ≥ 4. Substituting these bounds we get,
u(w) ≤

(η1 k)β+1 − 1
+ c1 wη1β+1
η1 k − 1

Maximal Layers Problem

Were c1 < 5 is a constant. Thus,
u(w) ≤

(η1 k)β (η1 k)
+ c1 wη1β+1
η1 k − 1

≤ c2 (η1 k)β + c1 wη1β+1

⌊log k w⌋+1

≤ c2 (η1 k)⌊logk w⌋ + c1 wη1

logk w

≤ c2 (η1 k)logk w + c1 wη1
log k w

≤ (c1 + c2 )wη1
Here, c2 ≤

14
9

and c3 are constants.

1

2

≤ c3 w1− log k +logk (1+ k+1 )

13

