All Questions
Tagged with mg.metric-geometry discrete-geometry
671 questions
2
votes
0
answers
73
views
Is parquetability decidable?
Let $T\neq \emptyset$ be a finite subset of $\mathbb{Z}\times\mathbb{Z}$. We say that $\mathbb{Z}^2 = \mathbb{Z}\times\mathbb{Z}$ is parquettable by $T$ if there is a partition $\frak P$ of $\mathbb{Z}...
- 63.9k
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 ...
- 415
3
votes
0
answers
117
views
Can a laser hit all the mirrors out of order?
For this question, a "cycle" is a sequence of distinct points
$X = (x_1,x_2,\cdots,x_k)\in\mathbb{R}^3$ which defines a piecewise linear path starting at $x_1$ and visiting the points in ...
- 63.9k
21
votes
2
answers
1k
views
Forbidden mirror sequences
Let $\cal{M}$ be a finite collection of two-sided mirrors,
each an open unit-length segment in $\mathbb{R^2}$,
and such that the segments when closed are disjoint.
A ray of light that reflects off the ...
- 2,821
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
3
votes
1
answer
386
views
Pointers/Papers on subdivision of planar quadrilateral meshes (PQ-Mesh) in 3D?
I'm interested in the subdivision of planar quadrilateral meshes (PQ-Meshes). Meshes consisting only of planar quadrilaterals, like discrete Voss surfaces and alike. I've been searching the web
for ...
- 1,446
1
vote
0
answers
85
views
More on triangles inscribed in convex regions with one vertex fixed
We add a bit to On maximum perimeter triangles inscribed in convex regions with one vertex fixed. Let C be a convex planar region and P a point on its boundary.
Are there convex shapes C other than (...
- 5,979
20
votes
0
answers
433
views
Is the dodecahedron flexible (as a polytope with fixed edge-lengths)?
Consider the (regular) dodecahedron $D\subset\Bbb R^3$. I want to continuously deform it so that throughout the deformation
it stays a convex polytope,
it stays a combinatorial dodecahedron (i.e. its ...
- 13.6k
1
vote
0
answers
77
views
Lattice packing
Let $\Lambda$ be a lattice in $R^n$ and $R>0$ a real number.
Consider the number $N$ of points in $\Lambda$ of norm less than $R$. Let $R$ goes to infinity. What can be said about the asymptotic ...
- 63.9k
3
votes
1
answer
116
views
Distance of average of points to center of minimum enclosing ball
Let $v_1, ..., v_n$ be distinct points in $\{0,1\}^d$ with the same norm $\|v_i\|_2=k$ (i.e each $v_i$ has $k$ ones). Let $A=\frac{1}{n}\sum_{i=1}^n v_i$ be their average, and let $C$ be the center of ...
- 45k
4
votes
1
answer
142
views
How many regular d-dimensional simplices of side length 1/2 are required to cover a regular d-dimensional simplex of side length 1?
For positive integers $n$ and $d$ satisfying $d = n-1$, let the $d$-dimensional regular simplex of side-length $\sqrt{2}$ be $X = \{(x_1, x_2, \cdots, x_n) \in \mathbb{R}^n: x_1+x_2+\cdots + x_n = 1, ...
- 4,713
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
6
votes
2
answers
215
views
Partition of polygons into 'strongly acute' and 'strongly obtuse' triangles
Definition: Let us refer to obtuse triangles with the largest angle strictly above a given cutoff value as 'strongly obtuse' - the definition is parametrized by the cutoff value. Likewise, strongly ...
- 63.9k
1
vote
0
answers
100
views
All 3-dimensional symmetric reflexive polytopes
$\DeclareMathOperator\Conv{Conv}$I am finding all 3-dimensional symmetric reflexive polytopes. To do so, first, we know that all 2 dim symmetric reflexive polytopes are $X_3=\Conv((-1,-1),(1,0),(0,1))$...
- 63.9k
2
votes
1
answer
190
views
Estimating the volume of a convex shape in higher dimensions based only on normal sections
We are given a $d$-dimensional convex shape $S$ inscribed in the hypercube $[-1,1]^d$. We want find an approximation of its volume based only on a set of curves given by the intersection of the $S$ ...
- 10.6k
4
votes
4
answers
536
views
Vertex-transitive polytopes in any dimension with any number of vertices?
Given positive integers $d$ and $v$ with $v \geq d+1$, does there always exist a (convex) vertex-transitive $d$-polytope with $v$ vertices? It seems that the answer should be "obviously" true, but I ...
- 1,502
1
vote
0
answers
48
views
Inside-out dissection
In a recent problem in The College Math Journal (1230) a Heronian triangle is called to have an equivalent rectangle if there exists an integer sided rectangle with the same area and perimeter. For ...
- 111
4
votes
2
answers
312
views
Which convex pentagon gives least packing density?
Among all convex pentagons, does the regular pentagon give least packing density?
Further question: For each $n > 6$, is the regular $n$-gon the minimum of packing density?
An analogous question ...
- 151k
1
vote
1
answer
96
views
A 'natural' enumerable metric space with integral distances which is essentially the Euclidean space
It is easy to construct a metric space $E_d$ such that all points
of $E_d$ are at mutually integral distance and such that there is a map $\varphi$ from $E_d$ into the $d$-dimensional Euclidean space ...
- 12.9k
13
votes
3
answers
388
views
Intersecting cylinders around a sphere
Intersecting $n$ unit-radius cylinders, each with axis through the origin,
produces a shape circumscribed about a unit-radius sphere:
My question is:
For each $n$, which arrangement of cylinders ...
- 52.3k
5
votes
1
answer
430
views
Volume of a shape whose boundary consists of portions of spheres symmetrically placed about the origin in $d\gg 1$ dimensions
We are given a convex shape $S$ in the $d$-dimensional Euclidean space, whose boundary is formed by portions of $2d$ different spheres, one portion per sphere. The radius of each sphere is the same, $...
- 1,677
15
votes
3
answers
9k
views
$n$-dimensional Voronoi diagram
I need to compute the Voronoi diagram of a set of points in $R^n$.
I'm quite unschooled on the topic, could someone point me to the right references so that I can
a) understand the theory behind it;
b)...
- 63.9k
7
votes
2
answers
393
views
Partitioning convex polygons into triangles of equal area and perimeter
This post is based on https://math.stackexchange.com/questions/2822589/dissect-square-into-triangles-of-same-perimeter, On a possible variant of Monsky's theorem and Cutting convex polygons into ...
- 2,821
16
votes
4
answers
2k
views
Point sets in Euclidean space with a small number of distinct distances
It is well known and not hard to prove that the regular simplex in n-dimensions is the only way to place n+1 points so that the distance between distinct pairs of points is always the same. My general ...
- 2,821
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\...
- 13.6k
34
votes
6
answers
8k
views
Covering a unit ball with balls half the radius
This is a direct (and obvious) generalization of the recent MO question, "Covering disks with smaller disks":
How many balls of radius $\frac{1}{2}$ are needed to cover completely a ball of ...
- 2,821
6
votes
3
answers
365
views
Sliding through a curvature-bounded tube: Maximum volume?
My 1st question has a straightforward answer but I'd appreciate hints on a proof. My 2nd question is open from my point of view.
Q1. Is it the case that the maximum convex volume body inside a ...
- 1,100
3
votes
0
answers
141
views
Optimal intersections between planar convex regions
Here is an earlier discussion that could be related:
On comparing planar convex regions of equal perimeter and area
We are broadly interested in placing two given planar convex regions so that the ...
- 5,979
15
votes
1
answer
838
views
Ratio of circumscribed/inscribed $(n{-}1)$-gons
As a discrete analog of the MO question,
"Löwner-John Ellipsoid: incribed and circumscribed,"
I've been wondering what might be the maximum ratio
of this quantity?
Let $P$ be a convex ...
- 2,821
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 ...
- 60.5k
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
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? ...
- 2,370
25
votes
3
answers
945
views
Are there arbitrarily large families of lines in $\Bbb R^3$ with average angle $\ge \pi/3$?
Question: Can I have an arbitrarily large finite family of lines $\ell_1,\dotsc,\ell_n\subset\Bbb R^3$ so that the average angle between two (distinct) lines is $\ge \pi/3$?
We can assume that all ...
- 156k
1
vote
1
answer
164
views
Partitioning convex polygons into quadrilaterals of equal area and perimeter
This post records a little bit more on this question: Partitioning convex polygons into triangles of equal area and perimeter.
The basic question of the above linked post was about this claim: "&...
- 3,068
3
votes
0
answers
53
views
Endpoints of intrinsic diameter of a convex polyhedron
Let $P$ be a convex polyhedron in $\mathbb{R}^3$, and $d(P)$ its intrinsic diameter,
i.e., the longest shortest surface path between two points. Say that $P$ is of
class
$D_0$ if neither endpoint of $...
- 151k
14
votes
7
answers
2k
views
Finite set of non-collinear points on plane with every point having ≥ 3 equidistant neighbors? [closed]
Does there exist a finite set of points on the Euclidean plane, such that:
No 3 points are collinear, and
Every one of the points has (at least) three other points in the set at the same distance ...
- 12.9k
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
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
5
votes
0
answers
177
views
Tiling with triangles of same circumradius and inradius
Consider a pair of positive real numbers $r$ and $R$ with $r<R/2$. Then we can form infinitely many triangles all with circumradius $R$ and inradius $r$.
For any such pair, the resulting triangles ...
CommunityBot
- 1
8
votes
2
answers
2k
views
Embedding points in 2D based on distance estimates?
Suppose we have a collection of exactly $N$ points (say $N=1000$), with each point belonging to 2-dimensional Euclidean space $\mathbb{R}^2$, but we don't know the coordinates of the points. Suppose ...
- 4,713
4
votes
1
answer
142
views
On polyhedrons with specified numbers of congruent faces
Basic question: Given 3 integers n, n1 and n2 such that n1+n2 = n, to form an n-face polyhedron such that n1 of its faces are mutually congruent and the remaining n2 faces are different but congruent ...
- 5,979
2
votes
1
answer
518
views
When can a folded polygon be isometrically (locally) embedded into R^3?
I am interested in 3-D representations of various things that naturally live in a non-simply-connected compact surface. There is the usual way of producing a compact surface of any orientable or non-...
- 4,713
6
votes
2
answers
544
views
On circles and ellipses drawn on an infinite planar square lattice
Consider a plane with a square lattice formed by all points with both coordinates as integers. As can be easily seen, a simple parabola can be found that passes through infinitely many of the square ...
- 5,979
21
votes
5
answers
1k
views
Is a rhombus rigid on a sphere or torus? And generalizations
If a rectangle is formed from rigid bars for edges and joints
at vertices, then it is flexible in the plane: it can flex
to a parallelogram.
On any smooth surface with a metric, one can define a ...
- 4,713
3
votes
1
answer
94
views
Convex polygon shadows: Shortest equivalent segments
Let $P$ be a convex polygon.
Q1. What is the shortest collection of line segments $S$ inside $P$
with the property that both $P$ and $S$ have the same sequence of orthogonal shadows
as $P$ and $S$ ...
- 6,101
16
votes
1
answer
888
views
Kakeya crossed-needles problem
The Kakeya needle problem asks for the
minimum area planar region in which one can completely turn around a line segment through
a series of translations and rotations. There is no minimum: There are &...
- 151k
24
votes
1
answer
770
views
Given a group action on a simplex, can I always find a fundamental region that is a simplex?
Let $\Delta\subset\Bbb R^n$ be a simplex with $n+1$ vertices. Let $G\subset\mathrm{GL}(\Bbb R^n)$ be a finite group of linear symmetries of $\Delta$, i.e. linear transformations that fix the simplex ...
- 156k
22
votes
1
answer
696
views
Rational inscribed realization of the regular dodecahedron
While it is clear that the regular dodecahedron $D$ cannot be realized with all integer coordinates, it is easy to find a polytope, which is combinatorially equivalent (face lattice isomorphic) to $D$ ...
- 12.4k
3
votes
1
answer
152
views
Triangles that can be cut into mutually congruent and non-convex polygons
It is easy to note that an equilateral triangle can be cut into 3 mutually congruent and non-convex polygons (replace the 3 lines meeting at centroid and separating out the 3 congruent quadrilaterals ...
- 5,979