All Questions
Tagged with co.combinatorics mg.metric-geometry
246 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
2
votes
0
answers
48
views
Maximum coverage of an orthogonal polygon using $k$ rectangles
I have an orthogonal polygon (all edges are horizontal or vertical) which is convex (no holes in any row of column of the polygon).
I would like to cover as much as possible of this orthogonal polygon ...
- 21
6
votes
2
answers
539
views
Bound on the number of unit vectors with the same pairwise inner products
I want to know the bound on the number of unit vectors $v_i$ in $\mathbb{R}^n$ such that $\langle v_i, v_j\rangle=c$ for all $i\ne j$. I know this can be upper bounded by the number of equiangular ...
- 163
4
votes
2
answers
299
views
Is there a set of point $S \subset \mathbb R^2$ such that $|\{C: C \text{ is unit circle boundary }, |C \cap S| = 10\}| > |S|$
There are some blue points and red points on the plane such that in the boundary of every unit circle centered at one blue point there are exactly 10 red point. Can the number of blue points strictly ...
- 193
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
8
votes
1
answer
567
views
Joining the $2^k$ points of $\{0,1\}^k$ with the shortest tree
Let $k$ be a given positive integer, and then consider the unit hypercube $\{0, 1\}^k \subset \mathbb{R}^k$ (i.e., a $k$-dimensional "cube" in the well-known Euclidean space).
We need to ...
- 1,451
5
votes
0
answers
127
views
Does the permutohedron satisfy any minimal distortion property for graph metric vs Euclidean distance?
We can look on the permutohedron as a kind of "embedding" of the Cayley graph of $S_n$ to the Euclidean space. (That Cayley graph is constructed by the standard generators, i.e. ...
- 24.9k
3
votes
0
answers
109
views
What Cayley graphs arise as nodes+edges from "nice" polytopes and when are these polytopes convex?
The Permutohedron is a remarkable convex polytope in $R^n$, such that its nodes are indexed by permutations and edges correspond to the Cayley graph of $S_n$ with respect to the standard generators, i....
- 24.9k
10
votes
1
answer
355
views
Is the group of translations of an affine plane always commutative?
$\DeclareMathOperator\Dil{Dil}\DeclareMathOperator\Trans{Trans}\DeclareMathOperator\Col{Col}$An affine plane is a set of points $X$ endowed with a family $\mathcal L$ of subsets of $X$, called lines, ...
- 41.8k
11
votes
0
answers
488
views
Are there 100 points that are part of every half-density part of the plane?
Is there a configuration $P$ that consists of 100 points of the plane such that every $X\subset\mathbb R^2$ whose density is half contains an isometric copy of $P$?
I am deliberately being vague ...
- 18.7k
0
votes
0
answers
125
views
Naming convention for different type of triangulations
When studying random geometries and related mathematical/physical stuff conflicting naming convention pops up regarding the naming of the different ensemble types of triangulations (in general ...
- 183
4
votes
0
answers
70
views
A question about the existence of surjective contractions
A few years ago I was doing some research in origami, and was motivated to as the following questions:
Consider $\mathbb{R}^2$ with the Euclidean metric and Lebesgue measure. Does there exist a ...
- 384
2
votes
0
answers
162
views
Root system terminology
Let $\Phi$ be a root system. In a paper I'm writing, I need to work with subsets $\Phi' \subset \Phi$ satisfying the following two conditions:
For all $\lambda_1,\lambda_2 \in \Phi'$ and $c_1,c_2 \...
- 21
1
vote
0
answers
84
views
Number of polyhedral covers of a triangulation of $S^2$
For a given triangulation (combinatorial Type I. or Type II.) of a $2$-sphere, what is the number of unique polygonal covers with $n$ polygons where ($n$ goes from $2$ to $N$)?
Under polygonal cover, ...
- 183
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
0
votes
0
answers
65
views
Maximal number of times distance $1$ can occur among $n$ points in the plane [duplicate]
For $n\in\mathbb N$, let $f(n)$ be the maximal number of times distance $1$ can occur among $n$ points in the plane:
$$
f(n) = \max_{ \{ x_1,\ldots,x_n \} \subset \mathbb R^2} \# \big \{ i<j : \| ...
- 43.2k
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
5
votes
1
answer
230
views
Covering unit-radius balls with unit-diameter objects
Let $d$ be a norm-based metric in $\mathbb{R}^2$. We are given a $d$-ball with radius 1, and we would like to cover it with objects with diameter 1. How many objects are needed?
In the $\ell_1$ metric,...
- 3,549
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
7
votes
1
answer
193
views
Free median algebras and maximal linked systems
$\DeclareMathOperator\MLS{MLS}$Recall that the median operation, on the power set $2^Y$ of subsets of a set $Y$, is the ternary law $m(A,B,C)$ mapping a triple of subsets to the set of elements ...
- 63.9k
2
votes
0
answers
56
views
Classification of Moufang planes of real dimension 16
Incidence geometry is not really area of expertise so I'm asking here: are all Moufang planes of 16 dimension already classified?
I'm not just interested in the compact ones. Is there already a ...
- 295
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
7
votes
1
answer
186
views
$d$-ball approximation for $d\gg 1$ with a convex hull of random points on its boundary
Given a $d$-ball $\mathcal{S}^{d}$, let $P_n$ a set of $n$ points selected uniformly at random on the boundary $\mathcal{S}^{d-1}$ of $\mathcal{S}^{d}$. Let $\mathcal{C}_n$ the convex hull of $P_n$. ...
- 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
2
votes
1
answer
159
views
Do all compact manifolds admit geodesic tiling
Let $M$ be a compact Riemannian manifold. I'll call a set of non-empty subsets $C_1,\dots,C_N$ a geodesic tiling of $M$ if:
Each $C_n$ is closed (geodesically) convex hull of a finite number of $\{...
- 5,405
0
votes
1
answer
115
views
Invariance of Minkowski sum of sets
Given an euclidean space $E$, two sets $A,B\subset E$ and the action on $E$ of two groups $G_A,G_B$ such that $G_A A=A$ and $G_B B=B$, it is possible to generate a group that leaves invariant $A\oplus ...
1
vote
0
answers
154
views
Volume of a polytope as its degenerates to be lower dimensional
Consider a polytope $P$ defined by the usual inequalities $A\mathbf{x}\leq \mathbf{b}$; let me assume that $P$ is not contained in a proper subspace. A result which I believe to true, but am not ...
- 44.7k
4
votes
2
answers
150
views
$O(n^{2-\epsilon})$ bound on choosing $n$ points on the hypersphere to maximize $\pm 1$ weighted sum of their $\binom{n}{2}$ inner products
Given $n,d\in\mathbb{N}, n\gg d$, I'm looking for a bound on the maximum (or minimum) expected value of the following game:
Draw a vector $\epsilon\in\{\pm 1\}^{\binom{n}{2}}$, uniformly at random. ...
- 41
4
votes
1
answer
322
views
Combinatorics related plane geometry
There are $n$ men, standing one at each vertex of a convex $n$-gon. If they are allowed to move together along sides or diagonals of the polygon to reach another vertex, how many different ways are ...
- 201
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
0
votes
0
answers
64
views
Convexity of stars in a subdivision of a simplex
Are the stars of vertices in a barycentric subdivision of a (standard) n-simplex convex?
I assume that it must be valid, but concretely to prove it I come again and again to obstacles. Approaches so ...
- 1
1
vote
1
answer
616
views
Polynomial invariant — from product formula to monomial expansion
Context
This question deals with the polynomial invariant denoted by $ H_{n} $ in Maksym Fedorchuk and Igor Pak's 2004 paper Rigidity and polynomial invariants of convex polytopes (sections 7.6 and 9)....
- 149
9
votes
1
answer
200
views
Bi-partitioning $2n$ points on the plane with a straight line
Let $S$ be a set of $2n$ points in $\mathbb{R}^2$. Which is the maximum number of different bi-partitions of $S$ generated by a straight line?
More precisely, which is the maximum number of partitions ...
- 4,459
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
5
votes
1
answer
190
views
Number of distinct normalized vectors from the center of a hexagon in a hexagonal grid
Consider an infinite hexagonal grid composed of regular hexagons. Choose any hex to be the origin hex. Let n be a natural number.
Find an expression, in terms of n, for the number of distinct ...
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
4
votes
1
answer
245
views
Hausdorff dimension and critical exponent of words
What is the Hausdorff dimension of the subset $S_c \subset [0,1]$ of points such that the critical exponent of their binary expansion is $c$? It's clear that $\dim_H S_{\infty}=1$, but what can be ...
- 4,459
3
votes
1
answer
206
views
Random planes separating points in $\mathbb{R}^3$
We are given a unit origin-centered sphere $S$ in $\mathbb{R}^3$, and three points $\mathbf{x},\mathbf{y},\mathbf{z}\in S$. Let $\mathbf{h}$ be a point selected uniformly at random from $S$ and let $H$...
- 1,677