Questions tagged [convex-hull]
The convex-hull tag has no usage guidance.
12
questions
1
vote
0
answers
40
views
Detailed exposition for proof of Localization Lemma in paper "Random Walks in a Convex Body and an Improved Volume Algorithm"
I've begun reading the paper "Random Walks in a Convex Body and an Improved Volume Algorithm" by Lovász-Simonovits ('93). Although the paper for the most part is pretty self-contained and ...
- 111
3
votes
1
answer
107
views
Strongly polynomial time algorithm for shortest convex combination
Problem: Let $S$ be a finite set of vectors. Let $C$ be their convex hull. Compute $\operatorname{argmin}_{x \in C} \|x\|$.
Reference 1 gives an algorithm for this problem that is finite-time (Section ...
- 652
1
vote
0
answers
72
views
How to enforce convexity?
I have a problem for which the solution is known to be a convex $f:[a,b]\times[c,d] \rightarrow \mathbb{R}$ over some rectangular domain ($a<b$ and $c<d$). There are many situations (e.g. ...
- 111
4
votes
1
answer
187
views
Restriction of a convex function to {0, 1}^n
Suppose I have a real-valued convex function $f$ on the unit hypercube $[0,1]^n$, and let $\bar{f}$ be its restriction to the integer points $\{0,1\}^n$. Does $\bar{f}$ satisfy any properties, or can ...
- 43
3
votes
1
answer
208
views
Convex polygons inclusion relation
I have the following problem which came as a subproblem in some work I was doing and I am completely stuck.
Note that I am interested in it only in terms of worst case time complexity (not heuristics ...
- 41
1
vote
0
answers
16
views
Size of solutions in integer programming
Given a linear integer program $Ax\leq b$ with $A\in\mathbb Z^{m\times n}$ and $b\in\mathbb Z^m$ known is there a polynomial time algorithm to give tight upper bounds for $\log_2\|x\|_\infty$ and $\...
- 12.8k
5
votes
0
answers
302
views
Total time complexity of convex hull problem
The convex hull problem is to compute the facets of the convex hull of finitely many given points in $\mathbb{R}^d.$ By cone polarity it is equivalent to computing the vertices and rays of a ...
user17918
2
votes
1
answer
533
views
maximizing inner product
Given two lists $L,L'\subseteq\mathbb{R}^d$ of $n$ vectors each,
how fast can we compute for all $p\in L$ the vector of $L'$ that maximizes the inner product with $p$, i.e., $\arg\max_{p'\in L'} \...
- 1,085
1
vote
0
answers
87
views
Convex hull of codebook (LP-decoding)
So the well-cited article by Feldman et al from 2005 has a method of constructing the convex hull of the feasible set for ML-decoding.
Basically, he considers the parity check matrix $H$ as a Tanner ...
- 263
2
votes
1
answer
258
views
When can a convex function induce submodularity?
Say I have a real valued convex function $f$ on the hypercube $[-1,1]^n$. Let $f'$ be the induced function on the discrete hypercube $\{-1,1\}^n$. Now I want to find a vertex on $\{-1,1\}^n$ on which ...
- 644
1
vote
0
answers
29
views
Extending Delaunay graphs in d-space
I am new to computational geometry so pardon me for the lack of formalism. I am currently experimenting with an algorithm of mine in which I need to extend recursively a Delaunay graph in $d$-space.
...
- 173
3
votes
1
answer
1k
views
Time complexity of d-dimensional convex hull
Consider the convex hull problem in $\Re^d$:
Input: a list of $n$ points $S$ in $\Re^d$,
Output: the vertices of the convex hull of $S$.
What is the best lower bound on the time complexity of ...
user22369