All Questions
109 questions
9
votes
0
answers
144
views
Which polytopes have compact realization spaces?
Let $P\subset\Bbb R^d$ be a convex polytope.
Its reduced realization space is the space of all combinatorially equivalent polytopes modulo projective transformations.
I am interested in polytopes for ...
- 13.6k
0
votes
0
answers
176
views
How to find a configuration of lines
In $\mathbb{R}^3$, can anyone help find a configuration of 5 lines such that the minimum of the smallest semi-axis lengths of the ellipsoid $ \mathbf{x}^T \mathbf{A} \mathbf{x} = 1 $, where $\mathbf{A}...
- 61
4
votes
0
answers
66
views
Convergence of graph geodesics to geodesics on metric spaces
Let $(X,d)$ be a compact length space metric space $\mathbb{X}_{\delta}$ be a $\delta$-packing on $X$ and, for every $k\in \mathbb{N}_+$, let $G_{k,\delta}=(\mathbb{X}_{\delta},\mathcal{E}_k,W_k)$ ...
- 364
1
vote
0
answers
67
views
Conjecture on the increasing efficiency of the shortest minimum-link polygonal chains covering any grids of the form $\{0,1,2\}^k$ as $k$ grows
From the well-known Nine dots problem, we know that we need a polygonal chain with at least $4$ edges to connect the $9$ points of the planar grid $G_{3,2}:=\{\{0, 1, 2\} \times \{0, 1, 2\}\} \subset \...
- 1,451
0
votes
0
answers
82
views
On 'Bisecting sections' of 3D convex bodies
Following shadows and planar sections, we ask about bisecting sections. This post also continues Convex planar regions with all area bisectors having equal length and A claim on the concurrency of ...
- 5,979
4
votes
1
answer
298
views
Does Kalai's $3^d$ conjecture hold for simplicial spheres?
Kalai's $3^d$ conjecture asserts that every centrally symmetric $d$-polytope has at least $3^d$ non-empty faces. This is open in general, but has been proven for simplicial polytopes.
Question: Does ...
- 13.6k
4
votes
0
answers
222
views
What does it mean "parallel"?
I am thinking on a strict definition of the notion of parallel affine sets in a linear space and came to the following
Definition 1: An affine set $A$ is parallel to an affine set $B$ in a linear ...
- 41.8k
5
votes
1
answer
397
views
How much of an aperiodic tiling is needed to force aperiodicity?
Consider an aperiodic tiling. By definition, there is a $C$ such that, for any box of side $C$, the part of the tiling contained in the box can be continued to the whole plane only in a non-periodic ...
- 20.2k
1
vote
1
answer
221
views
What properties are preserved by quasi-isometries
Recently, I came across the notion of quasi-isometries, while thinking of "discrete spaces which are surrogates for approximate continuous ones".
What (metric)/geometric properties are ...
- 5,405
3
votes
0
answers
187
views
Approximating any $d$-dimensional convex shape that occupies a constant fraction of its bounding box with a polytope having $\mathrm{poly}(d)$ facets
Given any convex set $A\in\mathbb{R}^d$, we denote by $V(A)$ its $d$-volume. Furthermore, given any two convex sets $A_1,A_2\in\mathbb{R}^d$, we denote by $V_{A_1,A_2}$ the $d$-volume of the symmetric ...
- 1,677
7
votes
0
answers
162
views
Approximating any convex shape in $\mathbb{R}^d$ with a polytope having $\mathrm{poly}(d)$ facets
We denote by $V(A)$ the $d$-volume of any convex set $A$. Furthermore, given any two convex sets $A,B\in\mathbb{R}^d$, we denote by $V_{A,B}$ the $d$-volume of the symmetric difference $V\left(A \...
- 1,677
1
vote
0
answers
111
views
Maximizing the minimum curvature of a convex shape with a given volume in higher dimensions
Given any $d$-dimensional convex shape $S$ in the Euclidean space with $d\gg 1$, let $K_{\min}(S)$ be the minimum value of the Gaussian curvature of its boundary.
Question: What is the maximum value $...
- 1,677
3
votes
1
answer
218
views
Bounding the number of facets of a polytope to approximate a given convex shape in higher dimensions
We are given a convex shape $S$ lying inside the hypercube $[0,1]^d$ in the $d$-dimensional Euclidean space. Let the volume $V(S)$ of $S$ be $\tfrac12$ (I guess nothing changes for any other fixed ...
- 1,677
4
votes
0
answers
144
views
Approximation of a convex shape in the $d$-dimensional Euclidean space for $d\gg 1$
We are given a convex shape $C$ lying inside the hypercube $[0,1]^d$ in the $d$-dimensional Euclidean space. Let the volume of $C$ be $\tfrac12$ (I guess nothing changes for any other fixed constant ...
- 1,677
0
votes
0
answers
49
views
When can a compact metric space be covered by finitely many nearly-disjoint closed and convex sets?
This question is a follow-up of the following negative question.
Let $(X,d)$ be a (non-empty) compact metric space.
More generally than in the first post, I'll call a set of non-empty subsets $C_1,\...
- 5,405
8
votes
1
answer
361
views
Inscribed $n$-polytope with $2^n$ vertices of maximal volume
The question is in the title:
Question: Which inscribed $n$-dimensional polytope (inscribed in the unit sphere) with $2^n$ vertices has the largest possible volume?
Is it the $n$-dimensional cube? ...
- 283
6
votes
1
answer
388
views
Covering number estimates on closed Riemannian manifolds
Let $(M^n,g)$ be an $n$-dimensional compact and connected Riemannian manifold with sectional curvature bounded above and below by $c,C$. Is it possible/known how to express the external covering ...
- 195
2
votes
1
answer
84
views
What is the average component size of a coloring?
Supose each cell of a big (or infinite) grid is colored at random by one of $k$ colors. Then the connected monochromatic components (here components are not supposed to contain "wasp waists",...
- 13.4k
7
votes
0
answers
254
views
Set of unit vectors such that among any three there is an orthogonal pair
I was fascinated by the solutions of Problem 8 of the IMC 2021 contest, which can be summarized as:
Theorem 1. Let $v_1,\dotsc,v_N$ be distinct unit vectors in $\mathbb{R}^n$ such that among any three ...
- 105k
21
votes
3
answers
935
views
Cutting of a regular polygon into congruent pieces
Question. For which $N$ it is possible to cut a regular $N$-gon into congruent pieces such that the center of the regular polygon lies strictly inside one of the pieces? For $N=3,4$ there are trivial ...
- 691
5
votes
0
answers
235
views
Arrangement of points, lines, and planes
Is it possible to construct a finite nontrivial arrangement of points, lines, and planes in 3-dimensional Euclidean space with the following properties?
every line is incident with four points and ...
- 2,773
22
votes
2
answers
900
views
Is every 1-million-connected graph rigid in 3D?
It is an old result that every $6$-connected graph is rigid in $\mathbb{R}^2$:
Lovász, László, and Yechiam Yemini. "On generic rigidity in the plane." SIAM Journal on Algebraic Discrete ...
- 151k
2
votes
0
answers
131
views
Maximum number of regions in a disk partitioned by pairs of parallel chords
We are given a disk $D$ in $\mathbb{R}^2$. Let $C$ be its boundary (i.e., the circle bounding $D$ on its plane). Let $P(n,d)$ be a set of $n$ pairs of chords of $C$ such that for each $\{c,c'\}\in P(n,...
- 1,677
5
votes
0
answers
190
views
The existence of $n$-sided cells in regular $m$-gons
For any integer $n >= 3$, does there exist a regular
$m$-gon with all diagonals drawn containing a cell with $n$ sides?
See A342222 and its cross-references.
Regular polygon on the Wiki.
&...
- 251
2
votes
1
answer
151
views
Given an input point in $\mathbb{R}^n$, select (one of) the closest point(s) from a fixed large set of points given in advance
We are given a set $S$ of $m\gg 1$ points in $\mathbb{R}^n$.
In the problem I am trying to solve, in a sequential fashion, we obtain a new point $p_r\not\in S$ at each round $r\ge 1$ and the goal is ...
- 1,677
2
votes
1
answer
143
views
Triangles and convex hulls in high dimensions
Given a set $S_n$ of $n$ points $\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n\in\mathbb{R}^d$, such that every $(d+1)$-tuple in $S_n$ is affinely independent, and let $C(S_n)$ be the convex hull ...
- 1,677
1
vote
0
answers
124
views
Number of lattice points in a structural symmetric convex body
Let $f$ is a convex symmetric function on the interval $[-a,a]$, i.e., $f(-x)=f(x)$ for $\forall \, x\in [-a,a]$. Then we consider a $n$-dimensional convex body in Euclidean space
\begin{equation}
\...
- 550
22
votes
1
answer
886
views
Happy ants never leave compact domain?
I am curious if the following seemingly simple question has an easy answer?
Consider an ant population of $N$ ants that lives in $\mathbb R^2$. Each ant can be labeled by some coordinate $x\in \mathbb ...
- 124
3
votes
1
answer
143
views
Combinatorial Euclidean geometry problem
Let $\mathcal{S}^d_{\epsilon}$ be the collection of all sets $S:=\{\mathbf{x}_1, \mathbf{x}_2, \ldots \mathbf{x}_{d+1}\}$ of $d+1$ points in a $d$-dimensional Euclidean space such that, for a given ...
- 1,677
3
votes
2
answers
438
views
If a polytope is centrally symmetric and combinatorially equivalent to a zonotope, is it a zonotope?
A zonotope is a polytope whose 2-faces are centrally symmetric.
Question: If a polytope $P$ is centrally symmetric and combinatorially equivalent to a zonotope, is it itself a zonotope?
- 13.6k
2
votes
1
answer
404
views
Euclidean distance bound with geometric constraints
Let $S_n$ be a set of $n$ points belonging to $\mathcal{B}_d:=\{\mathbf{x}\in\mathbb{R}^d:\|\mathbf{x}\|_2\le 1\}$, where $d\ll \log(n)$.
Let $s_n$ and $\ell_n$ be respectively defined as follows:
$$...
- 1,677
9
votes
1
answer
160
views
Hyperplane arrangements whose regions all have the same shape
Suppose I have a (finite, real, central, essential) hyperplane arrangement $\mathcal{H}$ such that all regions "have the same shape": for any two regions $R,R'$, there is an orthogonal ...
- 2,753
2
votes
0
answers
131
views
Optimal way to group points in the plane into clusters
Consider a strictly decreasing sequence $d = (d_k)_{k\ge 1}$ of distances in $(0,1)$. Given a constant $C>2$, we say that $d$ has the $C$-grouping property if any finite non-empty subset $S$ (of ...
- 1,761
1
vote
0
answers
81
views
Constructive way to optimally cover a compact subset of Euclidean space
Let, $(X,d)$ be a simply connected compact subset of $\mathbb{R}^d$ with non-empty interiorn, let $d$ denote the Euclidean metric, and let $\varepsilon>0$. Is there a way to iteratively select ...
- 5,405
5
votes
1
answer
114
views
Packing in uniform domains
Given $N$ points $X:=(x_i)_{i \in \{1,..,N\}}$, we now define a score function $S:X \rightarrow \mathbb{N}$ that is $S(X)= \sum_{i=1}^N S(x_i)$ where the score of $S(x_i)$ is
$$S(x_i) = 2* \vert \{x_j;...
- 536
4
votes
3
answers
347
views
Minimal data required to determine a convex polytope
Let $P\subset \Bbb R^d$ be a convex polytope.
Suppose that I know
its combinatorial type (aka. the face-lattice),
the length $\ell_i$ of each edge, and
the distance $r_i$ of each vertex from the ...
- 13.6k
5
votes
0
answers
313
views
Trade-off between covering number, ball radius and diameter of $d$-dimensional shapes
Given any $d$-dimensional shape $X$ in the Euclidean space, let $\ell(X)$ be the length of the longest line segment connecting two points of $X$. How can we prove the following statement?
There exists ...
- 1,677
3
votes
0
answers
134
views
Two questions on counterexamples to Borsuk's conjecture and ball-packings
In 1933 Karol Borsuk conjectured the following
Can every bounded subset $E$ of $\mathbb{R}^d$ be partitioned into $(d+1)$ sets, each of which has a smaller diameter than $E$?
Whilst new to this ...
- 31
5
votes
0
answers
199
views
Existence of a honeycomb composed by nearly-hyperspherical $d$-dimensional cells having the same shape and size
Let $\mathcal{H}$ the class of all honeycombs composed by $d$-dimensional cells $C$ having all the same shape and size in a $d$-dimensional space $\mathcal{S}$.
Let $s(C)$ and $\ell(C)$ be ...
- 1,677
4
votes
1
answer
363
views
Trade-off between hypervolume and diameter of $d$-dimensional shapes having a hypercubic smallest bounding box
Given any $d$-dimensional shape $X$, let $V(X)$ be its $d$-dimensional volume, and let $\ell(X)$ be the length of the longest line segment connecting two points of $X$.
Let $\mathcal{S}_C$ be the set ...
- 1,677
4
votes
0
answers
246
views
Distance properties of the permutations of a set of points in a Euclidean space
We are given a set of $n$ distinct points $S=\{\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n\}$ in a Euclidean space $\mathbb{R}^d$, where the distance between two points $\mathbf{x}_i,\mathbf{x}_j\...
- 1,677
13
votes
2
answers
3k
views
How many squares can be formed by using n points?
How many squares can be formed by using n points on a 3 dimensional space?
Like using 4 points, there is 1 square be formed
Using 5 points, still 1 square
Using 6 points, 3 squares can be formed
- 241
5
votes
1
answer
361
views
What is known about the duals of cyclic polytopes?
What is known about the duals of cyclic polytopes, in particular, their facets (or equivalently, the vertex-figures of cyclic polytopes)?
In even dimensions, all facets of the dual are ...
- 13.6k
4
votes
1
answer
293
views
Number of points in a lattice and an oblong box
I have a very simple question in geometry of numbers. (It is a slight modification of Counting points on the intersection of a box and a lattice .) There's a bound I can easily prove, and it's good ...
- 20.2k
5
votes
2
answers
304
views
Is there a 4-polytope without 3-gonal and 4-gonal faces, other than the 120-cell?
The question is in the title:
Question: Is there any 4-dimensional polytope without 3-gonal and 4-gonal faces (of dimension two), other than the 120-cell?
I consider only convex polytopes (convex ...
- 13.6k
1
vote
2
answers
227
views
A question about dense sets
Suppose that $A$ is a given subset of $I=[0,1],\ $ and
$ \left\{ x_j = \frac{j}{m} \right\}_{j=0}^{m}\ $ is the $m$-partition of $I$, and $\nu(m)$ is the number of
$\ [x_{i-1},x_{i}]\ $ such that $\ [...
- 419
5
votes
1
answer
176
views
Orientations of triples of points in the plane
Given a finite indexing-set $I$ and a collection $P = \{P_i: \ i \in I\}$ of points in the plane no three of which are collinear, let $I_{(3)}$ denote the set of ordered triples of distinct elements ...
- 19.7k
4
votes
0
answers
81
views
Number of orders of distances between points on a line
Points $a_1, a_2, \dots, a_n$ on a line form a set from $n(n-1)/2$ distances between them. Suppose all that distances are different, numerating them from the shortest to the longest one we obtain some ...
- 1,431
6
votes
0
answers
247
views
An extension of Erdos' distinct distances problem based on circles of various radii
Consider a collection $C_1,C_2, \dots, C_n$ of circles in the plane and suppose that the center of $C_i$ is $o_i$ and the radius of $C_i$ is $r_i$. We will define the relative distance between the ...
- 24.7k
17
votes
4
answers
1k
views
Can I build infinitely many polytopes from only finitely many prescribed facets?
Given a finite set of convex $d$-dimensional polytopes $\mathcal P$, for some $d\ge 2$.
Question: Is it true that there are only finitely many different convex $(d+1)$-dimensional polytopes whose ...
- 13.6k