I'm reading Computational geometry book.

In exercise 4.9 of the mentioned book we encounter the following problem:

Suppose we want to find all optimal solution of 3d- linear programming with $n$ constraints. Argue that any algorithm for solving this problem have lower bound $\Omega(n\log n)$.

I try as follow: i think we can construct a reduction from 3d convex hull to this problem, such that extreme points of intersection of half-spaces is our optimal solution. And because of we must count all optimal solution due to lower bound $\Omega(n\log n)$. But i think my argument isn't true. Any help to verify my argument can be appreciated.

My second argument: Suppose over linear programming have no objective function, and all extreme points are our solution, and according ‪Michael Ben-Or theorem counting number of extreme point need $\Omega(n\log n)$.

  • $\begingroup$ I suggest you edit the question to show us the specific reduction you have in mind. Until you've done that, we can't really assess your argument. $\endgroup$
    – D.W.
    Commented Jun 29, 2021 at 20:49


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.