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 ...
user avatar
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 ...
user avatar
  • 4,493
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$ ...
user avatar
  • 5,712
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 ...
user avatar
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$. ...
user avatar
  • 5,712
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. ...
user avatar
  • 4,256
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$ ...
user avatar
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}}...
user avatar
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 ...
user avatar
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=\...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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+...
user avatar
  • 46

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