11

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 the support of $q$. Then the conjugate is $$ f^*_q(x) = \sup_p\ \langle x, p \rangle - \sum_{i = 1}^n{p_i\log(p_i/q_i)}. $$ where the supremum is over the ...


7

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 bound are still the best known on the combinatorial complexity of the resulting Voronoi diagram. Their algorithm runs in time $O(n^{3+\varepsilon})$, matching ...


6

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$ hyperplanes. The dimension is $d=2$ (and the number $k$ of separating hyperplanes is part of the input). This has been proved in: Nimrod Megiddo On the ...


5

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$ could be given by a separation oracle, rather than explicitly, and it is also possible to solve an appropriately formulated version for a polyhedron. Observe ...


5

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$. Compute the arrangement of $h_1,\ldots,h_n$ (the subdivision of three-dimensional space into vertices edges, faces, and cells). This can be done in polynomial ...


5

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. Theorem: For cyclic groups with order $p^kq$, where $p$ and $q$ are primes and $k\in \mathbb{N}$, the incidence matrix of elements and subgroups is totally ...


4

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}}\right)$. It is enough to show that $\psi^{**}(p)=\sup_{\lambda}\{\lambda^{T}p-\log\left(\sum_{x}q(x)e^{\lambda_{x}}\right)\}=D_{KL}\left(p\,||q\,\right)=\...


4

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 following relationship between sub-modularity and convexity: A set-function $F$ is sub-modular if and only if its Lovász extension $f$ is convex. For a proof see ...


3

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=\sum_{i=1}^np_i=\sum_{i=1}^nx_iw_i$, but on the other hand because of $1 = \sum_{i=1}^nx_i$ and $1 = \sum_{i=1}^nw_i$ we have $1 = \sum_{i=1}^n\sum_{j=1}^nx_iw_j$, ...


3

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 bound drops to near quadratic. See the work by Koltun and Sharir, I think.


2

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 time $O(n\alpha(n)\log n)$, where $n$ is the number of line segments, and $\alpha(n)$ is the inverse Ackermann function. The algorithm computes the boundary of ...


2

This is an answer just to record a solution to the problem. Given the polytope, I triangulate it without introducing new vertices. Then I generate for each simplex in the resulting simplicial complex many points in the interior with my second approach. Every coefficient vector will give distinct points because the vertices of the simplices are affinely ...


1

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 polyhedron. If a supporting hyperplane does not exists, you know that the point is contained in the polyhedron. Otherwise, the supporting hyperplane helps you to ...


1

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+1)k^2\log k$.


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