All Questions
Tagged with mg.metric-geometry discrete-geometry
671 questions
5
votes
1
answer
383
views
cover and hide with squares
I am studying two numbers, related to squares, that can characterize a polygon P:
MinCoverNumber = the minimum number of axis-aligned squares required to exactly cover P (the covering squares may ...
- 3,549
5
votes
1
answer
547
views
Cover of a n-simplex with balls
Consider a n-simplex. For each edge (i,j), consider a n-ball, such that vertices i and j are antipodal on this ball. Is the simplex covered by the union of these balls? Thank you.
- 195
5
votes
1
answer
247
views
Question on the exact largest minimum angle
Could anyone help find the EXACT largest minimum angle between any pair of lines among 5 lines passing through the origin in $\mathbb{R}^3$? Additionally, what is the exact largest minimum angle ...
- 61
5
votes
2
answers
441
views
Touching-tetrahedra graphs
Have the graphs representable by touching tetrahedra been explored?
Let $\cal T$ be a collection of tetrahedra in $\mathbb{R}^3$
with pairwise disjoint interiors.
Define a graph $G_{\cal T}$ to have ...
- 151k
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
5
votes
1
answer
246
views
Convex polyhedra with non-congruent faces
Question: Are there convex polyhedra wherein all faces are convex polygons with same area and perimeter and no two faces are mutually congruent?
Remarks: If the answer to above is "no", then,...
- 5,979
5
votes
2
answers
366
views
Infinitely long rods that touch one another
Background: The basic question as given in 'Research Problems in Discrete Geometry' By Moser, Brass and Pach (page 98) is: What is the max number of congruent infinite circular cylinders that can be ...
- 5,979
5
votes
2
answers
134
views
Is there a non-orthogonal linear deformation of a polytope that preserves edge-lengths and vertex-origin-distances?
Is there a polytope $P\subset\Bbb R^d$ (convex hull of finitely many points, not contained in a proper affine subspace), and a linear, but non-orthogonal transformation $T\in\mathrm{GL}(\Bbb R^d)\...
- 13.6k
5
votes
1
answer
177
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
5
votes
1
answer
307
views
Panning for gold nuggets: a type of isoperimetric problem
Let $C$ be a unit-radius circle in the plane.
Suppose you have a total length $L$ of string available, and
your task is to connect chords of $C$ using no more
than $L$ of string to minimize the ...
- 151k
5
votes
1
answer
406
views
Computational approach deciding whether a set of Wang Tile could tile the space up to some size
As an applied person, I'm facing one practical problem deciding whether a set of Wang tile could tile the plane periodically or aperiodically. Although both problems seem undecidable, but I'm on a ...
- 867
5
votes
2
answers
629
views
Approximate search space on a 5x5x5 cube with 3 different possible classes?
Hey all,
I read the meta, and I realize this question might be pretty elementary for this site, but I'm having trouble computing this, and I know it won't take too much insight for someone to give me ...
- 153
5
votes
1
answer
190
views
Finding a superbase in a lattice of Voronoi first kind
An $n$-dimensional lattice in $\mathbb R^n$ is said to be of Voronoi’s first kind if it there exists $n+1$ vectors $b_1,\cdots b_{n+1}$ (called the superbase) such that
$\{b_1,\ldots,b_n \}$ is a ...
user14875
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
5
votes
2
answers
267
views
A Voronoi Iteration Game
Let $P_i$ be a set of points in the plane and $P_{i+1}$ the corners of the Voronoi diagram of $P_i$. Start with some $P_1$ and iterate away. What happens? Can you choose a $P_1$ so the iteration goes ...
- 4,829
5
votes
2
answers
1k
views
regular polyhedra (and polytopes) in hyperbolic geometry, and generalisations
While there exist regular tesselations of the hyperbolic plane with arbitrary regular polygons, there are no new regular polyhedra in hyperbolic (3D) space. This being quite trivial, it is probably ...
- 3,630
5
votes
1
answer
532
views
Regular lattice polygons
Suppose I want to construct an $N$-gon in the plane whose vertices are integer lattice points, and which is close to a regular $N$-gon (which means, the ratio of longest to the shortest side is within ...
- 96.4k
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
Which pyramids fill space?
Let us define a pyramid as a convex polyhedron with one quadrilateral face and four triangular faces.
Question: How many pyramids (or families of pyramids) are known that can fill 3D space without ...
- 5,979
5
votes
1
answer
264
views
Is there a polytope with an essentially unique shape?
More percisely:
Question: Is there a (convex) polytope that has a unique realization up to, say, projective transformations?
I suppose I have to assume that it has more than $d+2$ vertices/facets if ...
- 13.6k
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
5
votes
1
answer
156
views
On folding a polygonal sheet
Consider a polygonal sheet $P$ of area $A$ with $N$ vertices (it material is not stretchable or tearable). Let $n$ be a positive integer >=2.
Question: Let $P$ lie on a flat plane. We need to fold ...
- 5,979
5
votes
1
answer
188
views
Transport tubes in a sphere
Let $S$ be a unit-radius sphere in $\mathbb{R}^3$.
Q0. Where should one place $3$ disjoint lines intersecting $S$ to minimize the maximum distance between
any two points in $S$, where distance is ...
- 151k
5
votes
2
answers
378
views
Light inside a polyhedron
I have two questions the same as Mostafa's Question:
Visibility of vertices in polyhedra
Suppose $P$ is a closed polyhedron in space (i.e. a union of polygons which is homeomorphic to $S^2$) and $X$ ...
- 628
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 ...
- 5,979
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
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
5
votes
0
answers
93
views
Which polytopes can be deformed while keeping their edge-lengths?
Let $P\subset\Bbb R^d$ be a convex polytope (a convex hull of finitely many points). Lets call it flexible, if it can be continuously deformed while
keeping its combinatorial type, and
keeping its ...
- 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
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
5
votes
0
answers
139
views
On convex regions containing (and contained within) a given triangle
Given an arbitrary triangle T.
How does one find the convex region C_M of largest area containing T such that T is also the largest area triangle that is contained within C_M?
Guess: for any T, ...
- 5,979
5
votes
0
answers
508
views
Longest simple path through hypercube corners
This is a variation on a previously answered question,
Longest path through hypercube corners.
Here I am seeking the longest simple (non-self-intersecting) path through
the unit hypercube's vertices,
...
- 151k
5
votes
0
answers
135
views
What is the maximal convex hull in $\mathbb R^3$ of a tree with fixed total length?
Denote by $\mathcal T_n$ the set of all trees on $n$ nodes. For a tree $T\in\mathcal T_n$, we assign to each edge a non-negative length such that the sum of all lengths is 1. Denote by $v(T)$ the ...
- 13.4k
5
votes
0
answers
311
views
Biggest (or large) rectangle in a polytope
I need an efficient method to construct a (hyper)rectangle inside a polytope with a lot of dimensions (say $100 < d < 1000$). Ideally I'd want the biggest possible rectangle, but as I don't ...
5
votes
0
answers
214
views
Visibility in a prime orchard
This suggests a variant on Polya's orchard problem.
That problem asks1
for which radius $\epsilon$ of trees at each lattice point within a distance $R$ of the origin block all lines of sight to the ...
- 151k
5
votes
0
answers
1k
views
N-balls covering n-balls
This question is a follow-on question from:
Covering a unit ball with balls half the radius
The questions are these:
Given an arbitrary dimension d, and a unit n-ball in d-dimensional Euclidean ...
- 151
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 ...
- 51
4
votes
2
answers
567
views
Realization spaces for regular convex polytopes
Q1.
Are there convex polytopes combinatorially equivalent to each of the regular polytopes
that are realized with integer vertex coordinates?
&...
- 151k
4
votes
1
answer
438
views
Perfect squaring of rectangles
A perfect squaring of a rectangle may be defined as a partition of the rectangle into finitely many squares all of which are mutually non-congruent. https://en.wikipedia.org/wiki/Squaring_the_square ...
- 5,979
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
4
votes
2
answers
88
views
From a point and continuing reflection in $2n+1$ points then midpoint of the end point and the first point is fixed
Given $2n+1$ fixed points: $A_1, A_2,....,A_{2n+1}$ and point $P$. Let $B_1$ is the reflection of $P$ in $A_1$, $B_2$ is the reflection of $B_1$ in $A_2$,...., $B_{2n+1}$ is the reflection of $B_{2n}$ ...
- 1,776
4
votes
2
answers
271
views
Centralizing four red vectors in six green sectors
Four red vectors are given, one per quadrant, $[0,90^\circ)$,
$[90^\circ,180^\circ)$, etc.
A rigid star of six green vectors separated by $60^\circ$
can be positioned at
$(\theta,
\theta+60^\circ,
\...
- 151k
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 ...
- 5,979
4
votes
1
answer
263
views
Knotted TSP tours in 3D?
In the plane, the Euclidean TSP tour never crosses itself—it is always a simple polygon.
I am wondering if there is a similar constraint for the Euclidean TSP tour
of points in $\mathbb{R}^3$.
...
- 151k
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
1
answer
159
views
Best polygonal approximation to a polynomial $\pm$ c
Let a planar region $R$ be defined
by the vertical range bounded by
a polynomial $f(x) \pm c$ with $c>0$ a constant,
and with $x$ varying between the smallest and largest
roots of $f(x)$.
For ...
- 151k
4
votes
1
answer
1k
views
Algorithm for the shortest path through all the points of a 2D cloud
I have an array of points with their coordinates X and Y. Each point represents a bus stop.
I need to sort the points in a sequence by giving them sequence numbers, so that the path from the first to ...
- 61
4
votes
2
answers
1k
views
Sphere - Symmetry and Triangulation [closed]
The sphere is symmetric with respect to any rotation. However, it loses this property as soon as it is triangulated. Are there sequences of triangulations that possess particular large symmetry groups ...
- 1,256
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 $\...
- 165