# Tagged Questions

**3**

votes

**1**answer

178 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

416 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

375 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

619 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

191 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

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

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