Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more

Questions tagged [convex-geometry]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
20 views

Detection of intersection between two $d$-dimensional convex polytopes with at most $N$ facets

I am looking for a reference on the current state-of-the-art algorithm(s) for detecting intersection between two $d$-dimensional convex polytopes, with time complexity depending on their number of ...
pyridoxal_trigeminus's user avatar
2 votes
0 answers
75 views

References for algorithms to compute approximating polytopes for arbitrary convex sets

There is a vast theoretical literature on approximating convex, compact bodies in $d$-dimensional space $\Bbb R^d$ by convex polytopes. One of the main results in this area is that under some mild ...
pyridoxal_trigeminus's user avatar
0 votes
0 answers
33 views

doubt about volume packing lemma for intersection of convex sets and lattices (repost from math SE)

Lemma 3.24 of Additive Combinatorics by Tao and Vu states the following: Let $\Gamma \subset \mathbb{R}^d$ be a lattice of full rank, let $V$ be a bounded open subset of $\mathbb{R}^d$, and let $P$ ...
aba's user avatar
  • 91
3 votes
0 answers
84 views

Enforcing general position in $2d$ linear programming

Let $(x_1, y_1), ..., (x_k, y_k)$ be $n$ points in $\Re^2$. For my sake, $k=20$. I am trying to set up a linear program to find a set of $k$ points in the plane $P$ that satisfy some linear ...
user3508551's user avatar
  • 1,153
1 vote
0 answers
42 views

Detailed exposition for proof of Localization Lemma in paper "Random Walks in a Convex Body and an Improved Volume Algorithm"

I've begun reading the paper "Random Walks in a Convex Body and an Improved Volume Algorithm" by Lovász-Simonovits ('93). Although the paper for the most part is pretty self-contained and ...
total dependent random choice's user avatar
3 votes
1 answer
112 views

Strongly polynomial time algorithm for shortest convex combination

Problem: Let $S$ be a finite set of vectors. Let $C$ be their convex hull. Compute $\operatorname{argmin}_{x \in C} \|x\|$. Reference 1 gives an algorithm for this problem that is finite-time (Section ...
user76284's user avatar
  • 662
4 votes
1 answer
194 views

Restriction of a convex function to {0, 1}^n

Suppose I have a real-valued convex function $f$ on the unit hypercube $[0,1]^n$, and let $\bar{f}$ be its restriction to the integer points $\{0,1\}^n$. Does $\bar{f}$ satisfy any properties, or can ...
Sean L.'s user avatar
  • 43
1 vote
0 answers
71 views

How can we prove what the shortest line between two points avoiding convex obstacles is? (visibility graphs)?

I came across the observation in russell & norvig's artificial intelligence book that the shortest path between two points while avoiding convex polygonal obstacles is a sequence of line segments ...
user49404's user avatar
  • 119
5 votes
1 answer
93 views

Complexity of computing the union of H-polytopes in three dimensions

Consider a set $P_1,\ldots,P_k$ of polytopes in $\mathbb{R}^3$, each given as an intersection of halfspaces with rational normals (in particular, they are all convex). We are also given a target ...
Shaull's user avatar
  • 5,646
3 votes
1 answer
247 views

Minimal number of hyperplanes needed to separate sets of points from one other set

Let $\mathbb{R}^d$ be our space. We have a single good set of points $g$, and a collection of bad sets of points $B$. We assume that for all $b \in B$ the convex hulls of $g$ and $b$ are disjoint. ...
orlp's user avatar
  • 885
2 votes
0 answers
153 views

Is the following problem in $coNP$?

Given an $n\times n$ matrix $M$ with $\mathbb Z$ entries is 'does an $\frac n2\times\frac n2$ minor of $M$ vanish?' in $\bf{coNP}$? At least one $\frac n2\times\frac n2$ minor non-vanish implies rank ...
Turbo's user avatar
  • 12.9k
1 vote
0 answers
17 views

Size of solutions in integer programming

Given a linear integer program $Ax\leq b$ with $A\in\mathbb Z^{m\times n}$ and $b\in\mathbb Z^m$ known is there a polynomial time algorithm to give tight upper bounds for $\log_2\|x\|_\infty$ and $\...
Turbo's user avatar
  • 12.9k
1 vote
0 answers
137 views

Hausdorff Distance and Convex Hull

Given two sets of points A and B, both in $R^d$, is there a relation between the convex hulls of A and B, i.e. conv(A) and conv(B), w.r.t. the Hausdorff distance between A and B? In other words, does ...
user43464's user avatar
  • 209
10 votes
1 answer
257 views

Is this "subgroup packing" polytope integral?

Let $\Gamma$ be a finite abelian group, and let $P$ be the polytope in $\mathbb{R}^\Gamma$ defined to be the points $x$ satisfying the following inequalities: $$\begin{array}{cl} \sum_{g\in G} x_g \...
Andrew Morgan's user avatar
6 votes
1 answer
162 views

Embedding points in Euclidean space into a box

If I give you a set of points in Euclidean space, is there a criterion to determine whether there exists a (potentially higher-dimensional) rectangular prism / box that has these points as their ...
Timothy Chu's user avatar
2 votes
1 answer
66 views

Finding a cell in an arrangement of simplices

My question is n-dimensional, but I will begin by dropping the problem down to two dimensions for clarity's sake. It regards defining what is a solution by defining one or more data points that are ...
AaronF's user avatar
  • 123
10 votes
0 answers
161 views

Which convex polytopes have volumes of polynomial bit-length?

A convex polytope is described as an intersection of halfspaces, given as inequalities between linear combinations of variables with rational coefficients. The volume computation problem for convex ...
a3nm's user avatar
  • 9,409
1 vote
0 answers
90 views

Do nested convex bodies have increasing "Volume/Surface Area" ratios? [closed]

Suppose we have two convex bodies $A$ and $B$, where $A \subseteq B$. Is it always true that $\mathrm{Vol}(A)/\mathrm{SurfaceArea}(A) \leq \mathrm{Vol}(B)/\mathrm{SurfaceArea}(B)$? It's true in all ...
Maximinus's user avatar
5 votes
2 answers
225 views

Voronoi Diagram of Lines

Let $S$ be a set of lines (or line segments) in $\mathbb{R}^3$. Consider the Voronoi diagram $VD(S)$. The best lower bound on the complexity of $VD(S)$ is $\Omega(n^2)$ and the best upper bound is $O(...
user36641's user avatar
3 votes
0 answers
126 views

Equivalence of weighted Minkowski sums

Given $n$ polytopes $P_1, \cdots, P_n$, each $P_i$ is given as the V-representation, i.e., a set of $m$ points as its set of vertices. Furthermore, consider a variant of the Minkowski sum (somehow ...
user35648's user avatar
7 votes
1 answer
637 views

Decide whether a point is a vertex of a polytope?

Inspired by the question, I would like to ask the following question: Input: A polytope specified by $\Theta=\{\vec{x}\mid A\vec{x}\leq b\}$, and its affine projection $f(\Theta)= \{(\vec{c}_1\cdot \...
maomao's user avatar
  • 1,345
1 vote
0 answers
85 views

Compute basis of vertex set of polytope

I am wondering whether there is an efficient algorithm to compute the basis of the set of vertices of a polytope. Formally, INPUT: a polytope $$\Xi=\{(\vec{a}_1\vec{x}+\vec{b}_1, \cdots, \vec{a}_m\...
user35648's user avatar
2 votes
1 answer
267 views

When can a convex function induce submodularity?

Say I have a real valued convex function $f$ on the hypercube $[-1,1]^n$. Let $f'$ be the induced function on the discrete hypercube $\{-1,1\}^n$. Now I want to find a vertex on $\{-1,1\}^n$ on which ...
Student's user avatar
  • 654
1 vote
1 answer
106 views

Assignment of values for a set

Consider the following problem: Input: the vertices of two $n$ dimensional axis-parallel cubes: $\times_{i=1}^{n} [a_i,b_i] \subseteq [0,1]^n$ and $\times_{i=1}^{n} [l_i,u_i] \subseteq [0,1]^n$. ...
Star's user avatar
  • 253
5 votes
0 answers
270 views

Intersection of Hamming Balls

I am interested in the volume of the intersection of two Hamming balls of radius say m/6 in m-dimensional space, the distance between whose centers is about \sqrt{m}. I would ideally like this to be a ...
Vinod's user avatar
  • 51
1 vote
0 answers
137 views

Orlicz Norm and a result on expectation

I am reading a paper which is mainly about Dobrushin's contraction coefficient and its generalization. In page 27, the following is defined: Consider an arbitrary, non-negative, convex function $\psi:\...
SAmath's user avatar
  • 425
8 votes
2 answers
5k views

A Question on Convex Conjugate Duality for KL Divergence

The convex conjugate of a function, say, $f:X\mapsto \mathbb{R}$ is a function $f^*:X^*\mapsto \mathbb{R}$ defined as $$f^*(x^*):=\sup_{x\in X} ~\langle x, x^*\rangle-f(x),$$ where $X^*$ is the ...
SAmath's user avatar
  • 425
3 votes
0 answers
189 views

Computing the convex hull of several polyhedra

Let $K_1,..., K_m$ be a set of $m$ polyhedra, with $K_i\subseteq \mathbf{R}^n$, for all $i\in [m]$, and each is described by a set of $poly(n)$ linear inequalities. How easy is it to compute an ...
Lior Eldar's user avatar
  • 1,224
10 votes
0 answers
299 views

Approximating a convex polyhedron, with fewer inequalities

I have a convex polyhedron $\mathcal{P}$, given by $n$ linear inequalities $a_i \cdot x \le c_i$ where $x$ is a $d$-dimensional vector over the non-negative real numbers. In other words, $$\mathcal{...
D.W.'s user avatar
  • 12.1k
3 votes
1 answer
133 views

Efficient algorithm for computing equally distributed points in polytope?

Given a $d$-dimensional (rational) convex polytope $P$ with vertices $v_1, \ldots, v_n$, I would like to compute many equally distributed points that lie in $P$. "Equally distributed" is of course not ...
Gregor's user avatar
  • 551
6 votes
1 answer
281 views

Why is the first step in the Lovasz-Vempala convex volume algorithm correct?

I've been reading about convex volume estimation, and have found the paper "Simulated Annealing in Convex Bodies and an $O^{*}(n^4)$ Volume Algorithm" by Lovasz and Vempala, which can be read here. ...
ymbirtt's user avatar
  • 335
3 votes
1 answer
278 views

Algorithm for testing if a point belongs to a sequence of convex set or not

I have a sequence of convex sets $C_\lambda$ for $\lambda \in \mathbb{R}$ such that for $\lambda_1 > \lambda_2$, we have $C_{\lambda_1} \subset C_{\lambda_2}$ (essentially a nested sequence of ...
Kcafe's user avatar
  • 151
4 votes
1 answer
146 views

Batch membership testing for convex polyhedron specified in vertex representation

I have a convex shape defined by a set of vertices (the so-called vertex representation of a convex polyhedron). I also have a large set of points and I would like to test which are contained in the ...
Simd's user avatar
  • 3,902
9 votes
1 answer
445 views

VC dimension of Voronoi cells in R^d?

Suppose I have $k$ points in $\mathbb{R}^d$. These induce a Voronoi diagram. If I assign to each of the $k$ points a $\pm$ label, these induce a binary function on $\mathbb{R}^d$. Question: what is ...
Aryeh's user avatar
  • 10.6k
4 votes
1 answer
199 views

Configurations from arrangement of lines

Suppose we have an arrangement of $n$ lines in the plane. This partitions the plane into regions. We can label each region by a string in $\{+1, -1\}^n$, where the $i$'th coordinate is +1 if the ...
arnab's user avatar
  • 7,000
4 votes
2 answers
193 views

On facets of 01-polytope

$0,1$-polytopse are fundamental objects in combinatorial geometry and comvex optimization. I am interested in the size of binary representation of hyperplanes to use in the framework of computational ...
echuly's user avatar
  • 549
2 votes
0 answers
88 views

Helly's number from biconvex functions [closed]

Helly's Theorem states the following. Suppose $X_1,X_2,...,X_N$ are convex sets in $\mathbb{R}^d$, such that for any index-set $I$ with $|I| \leq h(d) := d+1$, we have $\bigcap_{i \in I} X_i \neq \...
user693's user avatar
  • 195
0 votes
0 answers
127 views

Extended Formulaiton and Integer Programming

An extended formulation (EF) of a polytope $P\subseteq \mathbb{R}^d$ is a system of linear constraints $Ex + Fy = g, y\geq 0$ in variables $(x,y)\in \mathbb{R}^{d+r}$ where $E,F$ are real matrices ...
echuly's user avatar
  • 549
1 vote
1 answer
113 views

Expressing a set of 0-1 strings by Extended Formulation

Extended Formulation of a polytope $P \subseteq \mathbb{R}$ is a system of linear constraints which satisfies the following condition: $x \in P \iff \exists y\in \mathbb{R}^{d} \mbox{ such that } Ax + ...
echuly's user avatar
  • 549
4 votes
1 answer
133 views

Balanced partitioning of a set of axis-parallel 2D rectangles

Fix a constant $0<\alpha<1/2$. The problem is the following. Suppose there are $N$ axis-parallel rectangles on the 2D plane with weights $w_1, w_2,\ldots, w_N$ and with coordinates all in the ...
T. Huynh's user avatar
11 votes
0 answers
202 views

On preprocessing a convex polyhedron prior to sampling

Most of the algorithms for estimating the volume of a convex polyhedron $K \subset R^d$ assume the existence of an affine transform $T$ with the property that $$ B \subset TK \tilde{\subset}\ \...
Suresh Venkat's user avatar
14 votes
1 answer
895 views

Computing the Löwner-John ellipsoid of a polyhedron

The Löwner-John ellipsoid of a convex set $C$ is the minimum-volume ellipsoid (MVE) that encloses it. The ellipsoid can be computed using Khachiyan's method, and there are a number of approximations ...
Suresh Venkat's user avatar
4 votes
2 answers
3k views

Minimizing the maximum dot product among k unit vectors in an n-dimensional space

Suppose, we are given a set of $k$ unit vectors $v_1,\ldots,v_k$ in $\mathbb{R}^n$. Consider all possible dot products among distinct vectors $v_i \cdot v_j$, where $i \ne j$. Let, $$\alpha = \max_{1 ...
Arindam Pal's user avatar
  • 1,591
8 votes
2 answers
221 views

Generating a point in a rational polytope $P \subseteq R^k$ given a point in $P^\epsilon$

Consider a rational polytope $P$ that is defined by means of a separation oracle. That is, $P$ can be described implicitly as $P = \{x \in R^k: Ax \leq b, A \in Z^{m \times k}, b \in Z^m \}$, but ...
Guy's user avatar
  • 1,205
9 votes
1 answer
503 views

Algorithm for approximating convex bodies by a convex hull of ellipsoids

I am working in the field of structural engineering and I would like to find an efficient algorithm to construct an approximation (in the Hausdorff metric) of a convex body $K$ by the convex hull of $...
docBrown's user avatar
13 votes
2 answers
509 views

Learning triangles in the plane

I assigned my students the problem of finding a triangle consistent with a collection of $m$ points in $\mathbb{R}^2$, labeled with $\pm1$. (A triangle $T$ is consistent with the labeled sample if $T$ ...
Aryeh's user avatar
  • 10.6k
23 votes
3 answers
751 views

Convex Body with minimum expected l2 norm

Consider a convex body $K$ centered at origin and symmetric (i.e. if $x\in K$ then $-x\in K$). I desire to find a different convex body $L$ such that $K\subseteq L$ and the following measure is ...
Ashwinkumar B V's user avatar
6 votes
0 answers
362 views

Approximating the diameter of a convex set defined by semidefinite constraints

A convex subset $C$ of $\mathbb{R}^{n^2}$ is given as the set of positive semidefinite $n\times n$ matrices whose coefficients fulfill some affine equations. Now, if you want to minimize a linear ...
Vincent Nesme's user avatar
9 votes
1 answer
1k views

Computing volume of high-dimensional convex polyhedra

I am looking for software for computing/estimating volume of high-dimensional convex polyhedra. More specifically, I am interested in a program, which can handle bodies with $n$ vertices in $d$-...
Grigory Yaroslavtsev's user avatar