I stumbled over this little exercise on StackOverflow where the poster asks for an algorithm to find the biggest subset of a point cloud which contains only points that do not dominate each other.

$p_1(x_1,y_1)$ dominates $\,p_2(x_2,y_2)$ if $\,x_1>x_2$ and $\,y_1>y_2$

So I wondered what is the ideal way to order points to get the maximum amount of points not dominating each other. Since that could also be formulated as a similar equation problem I will look for the function describing the line of points with the length of the function as value factor:

What is the longest function $y=f(x)$, with $\,x,y \in [0,1]$, where no two points $\,p_1, p_2 \in f, p_1 \ne p_2$ dominate each other?

(I hope I formulated that about right)

My thoughts:

By drawing the blocked areas it becomes clear that the function has to be descending, so one could imagine a stair shape or a version of $\,\lim_{a\to \infty} a\cdot\tfrac{1}{x}$ which crosses in $f(0)=1$ and $f(1)=0$ the boundaries. That limits the maximal length of $\,f$ to $2$.

I hope you also have fun giving this one some spare minutes of your time and come up with a better solution than mine.

  • $\begingroup$ if you read some of the comments below the answers at the SO question, apparently the intended question was much simpler than what people thought on first reading $\endgroup$ – Will Jagy Aug 20 '18 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.