11
votes
Accepted
A Question on Convex Conjugate Duality for KL Divergence
To make it easier let's assume $X$ is finite, of size $n$ and associate the density of $Q$ with an $n$-dimensional vector $q$. Assume also that $q$ is everywhere positive - otherwise replace $X$ with ...
- 18.1k
7
votes
Voronoi Diagram of Lines
In 2010 Hemmer et al. gave an exact algorithm for the Voronoi diagram of lines in $\mathbb{R}^3$. In their introduction, they state that the $\Omega(n^2)$ lower bound and $O(n^{3+\varepsilon})$ upper ...
- 4,523
6
votes
Accepted
Minimal number of hyperplanes needed to separate sets of points from one other set
Your problem is NP-complete, even in the following two highly restricted cases:
The dimension $d$ is part of the input, and the question is whether you can separate set $B$ from set $G$ by $k=2$ ...
- 5,742
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,764
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,764
5
votes
Accepted
Complexity of computing the union of H-polytopes in three dimensions
Your problem is solvable in polynomial time, as the dimension is fixed (at $d=3$):
Let $h_1,\ldots,h_n$ be an enumeration of all the bounding hyperplanes of the
polytopes $P_1,\ldots,P_k$ and $Q$.
...
- 5,742
5
votes
Accepted
Is this "subgroup packing" polytope integral?
Andrew(the asker) and I had discussed this over email, and we have shown the conjecture is false. The polytope is not integral for Abelian groups, not even for cyclic groups.
On the positive side.
...
- 4,327
5
votes
Decide whether a point is a vertex of a polytope?
This answer expands on Chandra's comment, and on my follow up comment. The problem is indeed solvable in polynomial time. More general versions of it are also solvable in polynomial time: $\Theta$ ...
- 18.1k
4
votes
A Question on Convex Conjugate Duality for KL Divergence
An alternative proof:
Given that $\psi(p)=D_{KL}\left(p\,||q\,\right)$ is closed and convex we know that $\psi^{**}(p)=\psi(p)$.
One proposes $\psi^{*}(\lambda)=\log\left(\sum_{x}q(x)e^{\lambda_{x}}...
- 41
4
votes
Accepted
When can a convex function induce submodularity?
The notion of sub-modularity you use is non-standard. Usually you consider set functions with domain $\lbrace 0, 1\rbrace^n$. But to answer your questions, the Lovász extension establishes the ...
- 56
3
votes
Assignment of values for a set
The problem as stated now is solvable in linear time.
To see this, suppose $p\in P$ is such that there are $x\in X$ and $w\in W$ with $p_i=x_iw_i$ for all $i$. This means on the one hand that $1=\...
- 2,480
3
votes
Voronoi Diagram of Lines
The problem is still open, although some progress was made on related problems (see http://arxiv.org/abs/1312.2194). It is known that if you are willing to use an approximate metric then the upper ...
- 9,586
2
votes
Accepted
Finding a cell in an arrangement of simplices
If I am understanding your problem correctly, this is the problem of computing the face containing a given point in an arrangement of line segments. There is a randomized algorithm running in expected ...
- 18.1k
1
vote
Batch membership testing for convex polyhedron specified in vertex representation
Instead of testing each point individually whether it is contained in the convex polyhedron, you should search for a supporting hyperplane of the polyhedron which separates the point from the ...
- 111
1
vote
Accepted
VC dimension of Voronoi cells in R^d?
Please check Theorem 21.5, Section 21 in the book "A probabilistic Theory of Pattern Recognition (1996)" from Devroye, Gyorfi, and Lugosi. I think the following upper bound is valid: VC $\leq$ $k + (d+...
- 46
Only top scored, non community-wiki answers of a minimum length are eligible