Skip to main content
6 votes
Accepted

maximizing inner product

For three-dimensional vectors, construct the three-dimensional convex hull of the vectors in $L'$ in time $O(n\log n)$. The maximizer for a vector $v$ in $L$ is the point of the convex hull that is ...
David Eppstein's user avatar
6 votes
Accepted

Strongly polynomial time algorithm for shortest convex combination

It is known via a paper of De Loera, Haddock and Rademacher that a strongly polynomial time algorithm for finding a minimum norm point in a simplex implies a strongly polynomial time algorithm for ...
Chandra Chekuri's user avatar
6 votes
Accepted

Restriction of a convex function to {0, 1}^n

Any real valued function $g$ defined on $\{0,1\}^n$ can be extended to a convex function over $[0,1]^n$ (it is called the convex closure). See Dughmi's nice survey. The implication for your question ...
Chandra Chekuri's user avatar
3 votes
Accepted

Convex polygons inclusion relation

Here's an argument that you need time quadratic in the number of polygons. More precisely, you should not be able to find containing pairs among $n$ $k$-sided polygons in time $O(n^{2-\epsilon})$, for ...
David Eppstein's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible