14

As @TsuyoshiIto suggests, there is an $O(n\log n)$-time algorithm for this problem, due to Edelsbrunner and Preparata. In fact, their algorithm finds a convex polygon with the minimum possible number of edges that separates the two point sets. They also prove an $\Omega(n\log n)$ lower bound for the more general problem in the algebraic decision tree model;...


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


8

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


8

From any choice of a polytope $P$ in ${\mathbb R}^k$, $\epsilon$, and a point $q$ in ${\mathbb R}^k$ it is possible to find a polytope $\hat P$ in ${\mathbb R}^{k+1}$, together with an embedding of ${\mathbb R}^k$ into ${\mathbb R}^{k+1}$, such that $\hat P$ is within $\epsilon$ Hausdorff distance of (the embedded image of) $P$ and such that (the embedded ...


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


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


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


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

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


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


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

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

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.


3

It seems to me that it is enough to consider tangent lines from the '-1' points onto the convex hull of the '+1' points as the candidates for the sides of $T$ (let's say that '+1' points will be inner to $T$). Too bad, I can't publish images here. But picture this: $t$ is the tangent line to the convex hull that goes through some '-1' point. $A$ is the ...


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


2

If your goal is to find a point in $P$ or determine that $P$ is empty, why don't you do the following. Let $H$ be a set of half-spaces, initially empty. Let $x$ be a point, initially equal to $0^k$. Give $x$ to the oracle. If the oracle said $x \in P$, you've done. Otherwise, let $S$ be the violated half-space returned by the oracle. Let $y$ be the ...


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


1

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)=\...


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 \begin{equation} \label{equation:ExtForm} Ex + Fy = g, y\geq 0 \end{equation} 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 ...


1

You may want to look into the "Crust" and "Power Crust" algorithms from Amenta, et al. Rather than ellipsoids, it uses spheres, but I believe the concept is simliar as they are able to, at the limit, construct a water-tight body from an unorganized point-cloud. In their case the desire was to mesh the original intended shape from the medial axis created ...


1

If we restrict $K$ and $L$ to be both ellipsoids, then your problem can be solved to any accuracy with an SDP. I know this is not what you asked originally, but it seems we have no solution even for this restricted case, and maybe it can help in general. So let's say $E$ is the input ellipsoid and we are looking to find an optimal enclosing ellipsoid $J$. ...


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