Skip to main content

All Questions

Filter by
Sorted by
Tagged with
1 vote
0 answers
110 views

Upper bound on the diameter of a convex lattice n-gon with a given area

Given the area $A$ of ​​a strictly convex polygon with $n$ vertices with integer Cartesian coordinates, there are usually several non-equivalent polygons. The relationship between the area, the number ...
Hugo Pfoertner's user avatar
2 votes
1 answer
113 views

Existence of fine approximate of a convex body in $\mathbb R^d$ with convex hull of $\mathcal O(d)$ points

Let $K$ be a convex body in $\mathbb R^d$ which contains the origin and let $\theta \in (0,1)$. Question. Is it always possible to find $n$ points $x_1,\dotsc,x_n \in \mathbb R^d$ such that $$ \theta ...
dohmatob's user avatar
  • 6,853
10 votes
1 answer
3k views

Computionally efficient vertex enumeration for (convex) polytopes

Let $P \subseteq \mathbb{R}^d$ be an $\mathcal{H}$-polytope. The vertex enumeration problem asks for the set of vertices $V$ of $P$. Theoretically, the vertex enumeration problem for $P$ can be ...
Christopher's user avatar
3 votes
1 answer
292 views

How to find the vertices of the set $\{v_i\in \mathbb{R}:a_1\ge v_1\ge v_2\ge \cdots\ge v_n\ge 0,\ q_2\le \sum_{i=1}^n p_iv_i\le q_1\}$

I am given a set of inequalities $v_1\ge v_2\ge \cdots\ge v_n\ge 0$, $q_2\le \sum_{i=1}^n p_iv_i\le q_1$, with $\{p_i\}_{i=1}^n,\ q_1,q_2$ positive reals, and only one bound for the coordinates: $v_1\...
Samrat Mukhopadhyay's user avatar
16 votes
2 answers
5k views

Weighted area of a Voronoi cell

Let $X = \{ x_1,\dots,x_n\} $ denote a set of $n$ points in the unit square $S = [0,1]\times[0,1]$, and let $w = \{w_1,\dots,w_n\}$ denote a set of weights corresponding to the $n$ points in $X$. ...
Joord Jacobsen's user avatar
2 votes
1 answer
349 views

Several convex polytopes in a simplex; fix an extreme point for each; how many can be supported by a function monotonic on all line segments?

Sorry the title may be unclear. I do not know how to give it a good title..... Let $\Delta$ be a probability simplex of $R^N$; i.e. set of all points $x$ such that $x\geq0$ and $\sum_{k=1}^Nx^k\leq1$....
Yi-Hsuan Lin's user avatar
1 vote
0 answers
68 views

Projection of a polytope along 4 orthogonal axes

Consider the following problem: Given an $\mathcal{H}$-polytope $P$ in $\mathbb{R}^d$ and $4$ orthogonal vectors $v_1, ..., v_4 \in \mathbb{R}^d$, compute the projection of $P$ to the subspace ...
Alina's user avatar
  • 11
1 vote
0 answers
43 views

Vertex enumeration for polytope with a sparse halfplane description?

Say I have a (bounded convex) polytope $P\subset\mathbb R^d$ with description $Ax\le b$, where $A$ is sparse in the sense that there are at most $k$ nonzero entries in each row or column, where $k$ is ...
tuna's user avatar
  • 523
2 votes
1 answer
248 views

Choosing the weights of a Voronoi diagram -- is this function always the gradient of another function?

This question is related to the earlier question Weighted area of a Voronoi cell . As in that question, let $X = \{ x_1,\dots,x_n\} $ denote a set of $n$ points in the unit square $S = [0,1]\times[0,...
Tom Solberg's user avatar
  • 4,049
4 votes
1 answer
367 views

convex polyhedron in the unit cube

Let $P$ be a given finite set of points within the $n$-dimensional unit cube. A finite set $Q$ of points within the $n$-dimensional unit cube covers $P$ if $\operatorname{conv}(Q) \supseteq P$ where $\...
Stefan Kiefer's user avatar
5 votes
2 answers
153 views

Expressing a convex Polytope as a sublevel set of a function

Given an n-dimensional polytope $P$ in $\mathbb R^n$, Given as a convex hull of a finite set of points, $S$ I would like to construct an expliict formula for a function $f\colon \mathbb R^n \to \...
Yaniv Ganor's user avatar
  • 1,893
2 votes
0 answers
49 views

Algorithm for Finding the Center of an Optimal Stereographic Projection

given a fnite set $\mathcal{P}$ of points on a $n$-sphere $\mathcal{S}$ and, define a function $f:(s,\mathcal{P})\mapsto\mathbb{R}_0^+$, that maps each point $s$ on $\mathcal{S}$ to the $n$-volume $...
Manfred Weis's user avatar
  • 13.2k
0 votes
0 answers
52 views

Efficient sampling from a polytope with large number of contraints [duplicate]

As far as I know, the most popular way to sample from a polytope (in H-representation) \begin{equation} \mathcal{P} := \{z \in \mathbb{R}^n | (Az)_j \le b_j\; \forall j=1,2,\ldots,m\} \end{equation} ...
dohmatob's user avatar
  • 6,853