# Tag Info

9

This problem is known as the question of realizability of pseudoline arrangements by straight lines. An arrangement of pseudolines is an arrangement of $n$ curves in the plane, such that any two curves intersect exactly once. For pseudolines, you can define the same labeling as the OP does. Pseudoline arrangements are related to oriented matroids, and you ...

9

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 ...

8

According to Boyd, it's NP-hard: http://youtu.be/mNzu42FrlHo?t=41m3s

7

For your second question, the number of bits is $O(n^2 \log n)$ (i.e. $O(n\log n)$ per coefficient) and there are examples where it is $\Omega(n^2\log n)$, i.e. the bound is tight. See Corollary 26 here. The ideas are standard, and anyone who has seen an analysis of the ellipsoid algorithm will be familiar with this. Say you have a facet in the hyperplane ...

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 ...

6

Answer: $\alpha = - 1/(k-1)$. This value is attained when vectors $v_i$ are the vertices of a regular simplex, centered at the origin. This follows from symmetry: given a set of vectors $u_i$ consider new vectors $u_i'= \frac{1}{\sqrt{k}}\left( u_i \oplus u_{i+1} \oplus \dots \oplus u_{i-1} \right)$ (where we add up all vectors $u_i$ in the cyclic order ...

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

Consider the plane through the points $(1,0,0,0)$, $(0,1,0,0)$, $(0,0,1,0)$, $(1,1,1,1)$. If you add the origin to this set of points, the hyperplane is a facet of the convex hull. The equation is $x_1 + x_2 + x_3 - 2x_4 = 1$. The coefficient on $x_4$ is not $0$ or $\pm 1$.

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

This seems like a hard problem. You might be able to do something if the rectangles have some packing property. For example, if no point is covered more than $t$ times (for some constant T), and the rectangles are not too long and narrow. Then one can probably prove that a curve intersects $O( \sqrt{n})$ rectangles, using some $k$-ply planar separator ...

4

It is also unclear to me what $\epsilon$ means in that line of the paper. The approximation error for $Z(a_0)$ is never mentioned again; my interpretation is that the authors are saying the error is so small it can be ignored. The bound I get is: $$\tag{*} Z(a_0)=Z(2n) \geq (1-(2/e)^n \mathrm{poly}(n)) \int_0^\infty e^{-2nt} t^n \pi_n dt.$$ So the ...

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

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)=\... 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 The obvious algorithm is to use binary search. You'll need$\lg n$iterations of binary search, where$n$= the number of convex sets in your sequence. (If you have an infinite family of convex sets,$\lg(|f(x)|/\epsilon)$iterations are enough to approximate$f(x)$to within$\epsilon$.) In each iteration, for some value of$\lambda$, you test whether$x ...

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$.

1

An extended formulation (EF) of a polytope $P\subseteq \mathbb{R}^d$ is a linear system $$\label{equation:ExtForm} Ex + Fy = g, y\geq 0$$ in variables $(x,y)\in \mathbb{R}^{d+r}$ where $E,F$ are real matrices with $d,r$ columns respectively and $g$ is a column vector such that $x\in P$ if and only if there exists $y$ such that ...

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