# Given a list of points in 3-D choose $m$ points such that sum of maximum values of $x$, $y$ and $z$ coordinates among all chosen points is minimum

We are given a list $$L = {(x_1, y_1, z_1), \dots, (x_n, y_n, z_n)}$$ and an integer $$m \leq n$$.

The goal is to find a subset $$S \subseteq \{1,\ldots,n\}$$ of size $$m$$ which minimizes the following cost function:

$$\mathit{cost} = \max_{p \in S}(x_p) + \max_{p \in S}(y_p) + \max_{p \in S}(z_p).$$

Is there any subquadratic algorithm to solve the above problem?

This question was recently asked in hiring challenge for an internship in some company. The challenge is over. I have a working solution which runs in $$O(n^2 \log{n})$$.

Sketch of my algorithm

• Iterate over all points $$(x_i, y_i, j_i)$$ in non-decreasing order of $$x_i$$. Along with that maintain a sorted list $$S_1$$ of pairs $$(y_j, z_j)$$ such that there is a point $$(x_k, y_k, z_k)$$ in original list such that $$x_k\le x_i$$ and $$(y_k, z_k)=(y_j, z_j)$$. Perform all the following steps in each iteration.
• If $$|S_1| then we know that there can not be any list of $$m$$ points where maximum value across $$x$$ coordinate is $$x_i$$. (In case of multiple point having same $$x$$-coordinate value we will eventually find a match in next iterations. So no need to worry about it.)
• Now iterate over pairs $$(y_j, z_j)$$ ($$j$$ index is not related to one used in second step) in $$S_1$$ in non-decreasing order of $$y_j$$. Along with that we maintain another list of $$S_2$$ of values $$z_k$$ such that there is some pair $$(y_k, z_k) \in S_1$$ such that $$y_k \le y_j$$.
• Now, If $$|S_2|\ge m$$ then update our $$\mathit{ans}$$ with $$\min(\mathit{ans}, x_i + y_j + m^{th} \text{ largest value in } S_2)$$