<p>I am studying the (worst-case) complexity $C(n,d)$ required to solve the maximal vector problem: given a finite set $V$ of $n$ $d$-dimensional vectors, compute the set of undominated (a.k.a. skyline, pareto) vectors: </p>

<p>$$\{v\in V\mid \forall v'\in V\;\exists i\leq d.\, v.i&gt;v'.i\}$$</p>

<p>I am aware of the following upper bounds: </p>

<ul>
<li>$O(dn^2)$ (trivial algorithm)</li>
<li>$O(n(\log n)^{d-2})$ when $d\geq3$, $O(n\log n)$ for $d\leq 3$. <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.87.6761" rel="nofollow">On Finding the Maxima of a Set of Vectors, Kung et al'75</a></li>
<li>$O(n^{2.684})$ when $d=n$ <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.145.9691" rel="nofollow">Efficient algorithms on sets of permutations, dominance, and real-weighted APSP, Yuster'08</a>, which improves marginally a result of Matousek's IPL'91.</li>
</ul>

<p>As for lower bounds, I am only aware of one bound (tight when $d=2$):</p>

<ul>
<li>$C(n,2)\geq S(n)+n-1\approxeq n\log_2 n+n-1$ , where $S(n)$ is the number of comparisons required for sorting $n$ elements. <a href="https://archive.org/details/onfindingmaximal667yaof" rel="nofollow">On finding the maximal elements in a set of plane vectors, F.F. Yao, technical report UIUC'74</a></li>
</ul>

<p>Are other non-trivial bounds known? In particular lower bounds that refine Yao's for $d&gt;2$?</p>

<p>N.B.1 For the lower bound I am interested in a model where the only question available to access the data is "<em>is vector $v$ greater than $v'$ along dimension $i$?</em>".
Though I would still be curious about whether interesting bounds are known in other models (e.g. for integer valued vectors).</p>

<p>N.B.2 The above is about computational complexity, but I am also curious about results about the minimal number of comparisons required, apart from
Yao's lower bound and the trivial $dS(n)$ upper bound</p>

CC BY-SA 3.0
2014-02-05T20:01:30.010Z
What is a "question" in this setting ?
Suresh Venkat
CC BY-SA 3.0
2014-02-06T16:29:56.077Z
Thanks. I had not seen the bug at first. The nlog(n) lower bound on complexity for d=2 assumes comparison sort: a linear algorithm can be obtained if sorting is linear.
Joseph Stack
<ds.algorithms><reference-request><cg.comp-geom><optimization>
Lower bound for the maximal vectors problem
Joseph Stack
# Lower bound for the maximal vectors problem

(Asked by: username_0 on 2014-02-05)

I am studying the (worst-case) complexity $C(n,d)$ required to solve the maximal vector problem: given a finite set $V$ of $n$ $d$-dimensional vectors, compute the set of undominated (a.k.a. skyline, pareto) vectors:

$$\{v\in V\mid \forall v'\in V\;\exists i\leq d.\, v.i>v'.i\}$$

I am aware of the following upper bounds:

* $O(dn^2)$ (trivial algorithm)
* $O(n(\log n)^{d-2})$ when $d\geq3$, $O(n\log n)$ for $d\leq 3$. [On Finding the Maxima of a Set of Vectors, Kung et al'75](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.87.6761)
* $O(n^{2.684})$ when $d=n$ [Efficient algorithms on sets of permutations, dominance, and real-weighted APSP, Yuster'08](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.145.9691), which improves marginally a result of Matousek's IPL'91.

As for lower bounds, I am only aware of one bound (tight when $d=2$):

* $C(n,2)\geq S(n)+n-1\approxeq n\log\_2 n+n-1$ , where $S(n)$ is the number of comparisons required for sorting $n$ elements. [On finding the maximal elements in a set of plane vectors, F.F. Yao, technical report UIUC'74](https://archive.org/details/onfindingmaximal667yaof)

Are other non-trivial bounds known? In particular lower bounds that refine Yao's for $d>2$?

N.B.1 For the lower bound I am interested in a model where the only question available to access the data is "*is vector $v$ greater than $v'$ along dimension $i$?*".
Though I would still be curious about whether interesting bounds are known in other models (e.g. for integer valued vectors).

N.B.2 The above is about computational complexity, but I am also curious about results about the minimal number of comparisons required, apart from
Yao's lower bound and the trivial $dS(n)$ upper bound

**Tags:** ds.algorithms, reference-request, cg.comp-geom, optimization

> **Comments:**
> **username_1**: What is a "question" in this setting ?  
> **username_0**: Thanks. I had not seen the bug at first. The nlog(n) lower bound on complexity for d=2 assumes comparison sort: a linear algorithm can be obtained if sorting is linear.  

---

## 0 answers

