# Tagged Questions

**3**

votes

**1**answer

186 views

### Generalization of notion of convexity

I am searching for the correct term for the following, if it exists.
A set $X\subset \mathbb{R}^2$ is called $r$-convex if for any two points $x_1, x_2\in X$ such that there exists an arc of radius ...

**3**

votes

**3**answers

438 views

### How to find the minimum number of hyperplanes to define a convex hull?

I have the following problem:
I have a convex hull $\Omega$ defined by a set of n-dimensional hyperplanes $S = [(n_1,d_1), (n_2,d_2),...,(n_k,d_k)]$ such that a point $p \in \Omega$ if $n_i^T p \geq ...

**6**

votes

**2**answers

376 views

### Complexity of detecting a convex body in $\mathbb{R}^n$?

Let $K_0$ be a bounded convex set in $\mathbb{R}^n$ within which lie two sets $K_1$ and $K_2$. $K_0,K_1,K_2$ have nonempty interior. Assume that,
$K_1\cup K_2=K_0$ and $K_1\cap K_2=\emptyset$.
The ...

**1**

vote

**1**answer

624 views

### Applications of ham sandwich type results. References? A general principle?

Lately there has been a lot of interest on applications of the ham sandwich theorem and related results. There is a bunch of lecture notes and surveys that touch upon the subject. I dont know of any ...

**8**

votes

**1**answer

192 views

### Finding a point that lies in a majority of polytopes

Suppose I have $k$ $n$-dimensional polytopes $P_1,\ldots,P_k$, each explicitly specified as the intersection of a collection of hyperplanes. If there was a point $p \in \mathbb{R}^n$ that lay in the ...

**2**

votes

**1**answer

629 views

### Condition number for Ellipsoid method matrix

Hello,
When using the ellipsoid method (for solving a linear program for example), the volume of the ellipsoid at each iteration is proven to decrease, and do so by at least a factor of $e^{1/2n}$.
...

**5**

votes

**2**answers

335 views

### Heaviest Convex Polygon

Suppose we have an arbitrary function $f : \mathbb{R}^2 \to \mathbb{R}$. For any subset $s \subseteq \mathbb{R}^2$, we can define $g_f(s)$ as the integral* of $f$ over the region $s$. Suppose ...

**10**

votes

**3**answers

616 views

### Deciding membership in a convex hull

Problem: Given points $u,v_1,\dots,v_n\in\mathbb{R}^m$, decide if $u$ is contained in the convex hull of $v_1,\dots,v_n.$
This can be done efficiently by linear programming (time polynomial in ...

**15**

votes

**9**answers

7k views

### Algorithm for finding the volume of a convex polytope

It's easy to find the area of a convex polygon by division into triangles, but what is the optimal way of finding the volume of higher-dimensional convex bodies? I tried a few methods for dividing ...