Skip to main content

# Tag Info

## Hot answers tagged convex-hull

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 ...
• 51.1k
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 ...
• 6,999
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 ...
• 6,999
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 ...
• 51.1k

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