All Questions
Tagged with convexity discrete-geometry
21 questions
1
vote
0
answers
30
views
Finite right-triple convex sets in planes
Let $\mathcal{S}$ be a set of points in $\mathbb{R}^2$. We say that $\mathcal{S}$ is right-angle convex, if for any two distinct points $P,Q\in \mathcal{S}$ there always exists another point $R\in \...
- 123
3
votes
0
answers
208
views
Reference request: Carathéodory-type theorem for convex hulls of closed sets
I'm looking for a reference for the following theorem.
Theorem Let $X$ be a closed subset of $\mathbb{R}^N$, and let $a$ be a point of its convex hull $\operatorname{conv}(X)$. Then there exist ...
- 27.7k
1
vote
0
answers
95
views
Detecting points inside the convex hull with inner products
Given a finite set $P$ of $n\gt d+1$ points in $d$-dimensional euclidean space.
Under the assumption that the points of $P$ are in general position in the sense that $\lbrace p_{i_1},\dots,p_{i_d}\...
- 13.2k
2
votes
1
answer
308
views
Intersection of the simplex with a linear subspace of codimension $2$
The sets are defined in $\mathbb{R}_+^n$ $(n\geq 1)$. The relative interior of a convex set $C$ is denoted $\mathring C$.
Let $S$ be the $n$-simplex:
$$S=\left\{x\in\mathbb{R}_+^n,\,\sum_{i=1}^n x_i=1\...
- 449
69
votes
3
answers
12k
views
Nonconvexity and discretization
Edit: Here's a more down-to-earth, and somewhat weakened, but I believe still nontrivial, version of the main theorem.
Prototypical nonconvex spaces are $\ell^p$-spaces for $0<p<1$, say $\ell^p(\...
- 21.3k
6
votes
1
answer
295
views
A conjecture (or theorem?) on unit vectors in a Euclidean space
I have heard (if I am not mistaken) that there exists the following conjecture (or theorem?).
Let $u_1,\dots,u_n$ be unit vectors in an $n$-dimensional Euclidean vector space. Then there exists ...
- 21.8k
18
votes
2
answers
840
views
Reference to a conjecture on unit vectors in Euclidean space
I have heard that there exists the following conjecture (if I am not mistaken).
Let $u_1,\dots,u_n$ be unit vectors in an $n$-dimensional Euclidean vector space. Then there exists another unit vector ...
- 21.8k
4
votes
1
answer
115
views
What is the probability of an empty convex $k$-gon among many given points?
Given a finite number of points in the plane in general position, call a convex subset empty if its hull doesn't contain any other of the points.
For a big number $n$ of randomly distributed ...
- 13.4k
3
votes
1
answer
449
views
VC dimension under projection
Let $C$ be a family of convex sets in $\mathbb{R}^d$ and assume further that $C$ is closed under translation: for all $A\in C$ and $x\in\mathbb{R}^d$, we have $A+x\in C$.
Let $P:\mathbb{R}^d\to\...
- 6,541
10
votes
0
answers
418
views
Determining convexity of a polygon from its Fourier coefficients
Consider an $n$-sided polygonal curve in the plane, represented by an ordered set of points $(x_0, x_1, \ldots, x_{n-1})$; line segments connect consecutive points and also $x_{n-1}$ to $x_0$. It is ...
- 553
21
votes
2
answers
1k
views
On convergence of convex bodies
Let $K\subset \mathbb{R}^n$ be a compact convex set of full dimension. Assume that $0\in \partial K$.
Question 1. Is it true that there exists $\varepsilon_0>0$ such that for any $0<\...
- 21.8k
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,...
- 4,049
2
votes
1
answer
171
views
Distance from constant width bodies
EDIT As @David has observed, my conjecture was clearly wrong for $\ n:=2.\ $ Let me still give it a chance for $\ n\ge 3$.
I'll call a family $\ F\ $ of bound closed convex subsets of $\ \mathbb R^n\ ...
- 7,500
23
votes
2
answers
530
views
Trapping a convex body by a finite set of points
In $\mathbb{R}^n$, let $K$ be a convex body and $T$ a finite set of points disjoint from the interior of $K$. Say that $T$ traps $K$ if there is no continuous motion of $K$ carrying $K$ arbitrarily ...
- 7,276
1
vote
1
answer
176
views
Helly's number from biconvex functions
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 \...
- 135
2
votes
1
answer
296
views
Lipschitz Constant of the convex extension of a submodular function
The title says it all :)
Given a submodular function (take the rank function of a matroid, for a concrete example) $f:\{0,1\}^n\rightarrow \mathbb{R}$, we can extend it to a convex function $g:[0,1]^n\...
- 243
3
votes
1
answer
735
views
Tverberg partitions with less than (r-1)(d+1)+1 points
The Tverberg Theorem states the following: Let $x_1,x_2,\dots, x_m$ be points in $R^d$ with $m \ge (r-1)(d+1)+1$. Then there is a partition $S_1,S_2,\dots, S_r$ of $\{1,2,\dots,m\}$ such that $\cap _{...
- 278
7
votes
1
answer
387
views
Erdős-Szekeres empty pseudoconvex $k$-gons
I am wondering if the
Erdős-Szekeres
empty convex $k$-gon question has a different answer if
convexity is replaced by a pseudoline-version of convexity.
The empty convex $k$-gon question
is a variant ...
- 151k
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$. ...
- 195
2
votes
0
answers
164
views
Minimally 6-connected 3D discrete lines that are convex lattice sets
There are several definitions of 3D discrete lines, e.g. http://diwww.epfl.ch/w3lsp/publications/discretegeo/nratddl.html , http://dx.doi.org/10.1007/978-3-642-19867-0_4 . However, I know of none that ...
- 567
22
votes
3
answers
2k
views
Covering a circle with red and blue arcs
We have a circle and two families of $n$ red arcs and $n$ blue arcs, positioned on the circle so that every two arcs of different colors intersect. Can one show that there is a point in the perimeter ...
- 85.6k