All Questions
Tagged with mg.metric-geometry discrete-geometry
671 questions
4
votes
0
answers
443
views
Intersection of pencils in $\mathcal{R}^2$
Consider $9n$ pencils through non-collinear points $p_1, \ldots , p_{9n}$ in $R^2$ each consisting of at most $n$ concurrent lines. Define the intersection $S$ of these pencils to be the set of points ...
13
votes
2
answers
1k
views
Average degree of contact graph for balls in a box
Imagine you dump congruent, hard, frictionless balls in a box,
letting gravity compress the balls into a stable configuration
(I believe such configurations are called
jammed.)
Assume the box ...
- 151k
15
votes
1
answer
2k
views
Ping-pong relief map of a given function z=f(x,y)
I have an idea to design a type of
Galton's Board
to "draw" a relief map of a given two-dimensional function $z=f(x,y)$.
A typical Galton's Board drops, say, ping-pong balls through a series
of evenly ...
- 151k
16
votes
4
answers
3k
views
covering by spherical caps
Consider the unit sphere $\mathbb{S}^d.$ Pick now some $\alpha$ (I am thinking of $\alpha \ll 1,$ but I don't know how germane this is). The question is: how many spherical caps of angular radius $\...
- 96.4k
1
vote
2
answers
329
views
Can a set of tetrahedra glued together by a common vertex be isometrically embedded in R^4?
A collection of triangles with a common vertex $A_1VA_2$, $A_2VA_3$, ... $A_NVA_1$ with specified side lengths can be isometrically embedded in $R^2$ provided the angles around $V$ add up to $2\pi$. ...
- 221
22
votes
1
answer
663
views
Voronoi cell of lattices with the same profile
Definition 1. Given a body $V$ in $\mathbb R^n$,
the function $p_V\colon \mathbb R_+\to \mathbb R_+$
$$p_V(r)=\mathop{\rm vol} [V\cap B_r(0)]$$
will be called profile of $V$.
Definition 2. Define ...
- 45k
16
votes
1
answer
1k
views
Random polycube shapes
I am wondering if it is hopeless to obtain any firm results
on the following model of a "random polycube shape."
First, a polycube in $\mathbb{R}^3$
is a connected face-to-face gluing of unit cubes.
(...
- 151k
23
votes
3
answers
2k
views
Rolling-ball game
The analyses
in two recent MO questions
("recent" with respect to the original posting in 2011),
"Rolling a random walk on a sphere"
and
"Maneuvering with limited moves on $S^2$,"
suggest a Rolling-...
- 151k
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
15
votes
2
answers
737
views
Tiling survey that updates "Tilings and patterns"?
Can anyone suggest a survey (or surveys) that provides an update to Tilings and patterns by Grunbaum and Shepard? If there's a more recent book, that would be fantastic, but I don't see one.
I am ...
- 881
2
votes
1
answer
370
views
Large subgroups of the Hamming cube
Let's consider the abelian group $\mathbb{Z}^N_2$ equipped with the Hamming metric (the hypercube).
Suppose I have a subgroup of this hypercube (not necessarily a subcube) which is generated by a set ...
11
votes
3
answers
3k
views
polyhedra with equilateral pentagons faces
In page http://loki3.com/poly/isohedra.html around six polyhedra with equilateral pentagons as faces are shown: a pyritohedron, icositetrahedrons... Is there a complete list of this kind of polyhedra? ...
- 111
10
votes
2
answers
930
views
What is determined by the combinatorics of the shadows of a convex polyhedron?
Define the shadow of a convex polyhedron $P$ in direction $u$
to be the orthogonal projection of $P$ onto a plane whose normal is $u$.
The shadow is a convex $k$-gon.
I am wondering to what degree $P$ ...
- 151k
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 ...
- 133
8
votes
0
answers
358
views
Coloring toroidal polyhedra with convex faces?
Consider a toroidal polyhedron, which is a topological torus, in which all faces are planar, two faces meet in at most an edge, and adjacent faces are not coplanar. The Szilassi polyhedron has 7 non-...
2
votes
1
answer
1k
views
Sphere packing in a sphere
Let $S_a^d$ be the $(d-1)$-dimensional sphere of radius $a$ in $\mathbb{R}^d$. Let $r>0$ be a constant and $R=\nu r$ where $\nu>1$ (some constant). Are there any known upper bounds on the number ...
- 3,217
2
votes
0
answers
261
views
Existence of partitions of $S^{n-1}$ with hypercubes
For which value of the integer $n$ does there exist a partition of $S^{n-1}$, the unit sphere of $\mathbb{R}^n$ for the euclidean norm, by a family of images of the standard hypercube $C=\{ (e_1, ..., ...
45
votes
1
answer
2k
views
Pach's "Animals": What if the genus is positive?
Janos Pach asked a deep question 23 years ago (1988) that remains unsolved today:
Can every animal—a topological ball in $\mathbb{R^3}$ composed of unit cubes glued face-to-face—be ...
- 151k
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 ...
- 151k
88
votes
2
answers
7k
views
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)...
- 253
17
votes
4
answers
823
views
Sweep-segment bot: Will this random walk sweep the plane?
This model is inspired by the random behavior of the
Roomba sweeping robot.
Let a unit segment $ab$ in the plane be placed
initially with $a=(0,0)$ and $b=(1,0)$.
The segment is first rotated a ...
- 151k
3
votes
1
answer
236
views
Non-inherited symmetries of shadows of point sets
Sometimes a point set in Euclidean space may have a shadow with an unexpected symmetry. The purpose here is to ask when this happens or when it doesn't happen (in some generality).
This requires a ...
- 1,277
4
votes
1
answer
377
views
Discrete gradient ascent cycles
I am wondering what can be inferred when a discrete
gradient ascent algorithm gets stuck in a cycle.
Here is the situation.
A function $f(x,y)$ is defined over a range $[0,n]^2$,
and the algorithm ...
- 151k
45
votes
1
answer
3k
views
two tetrahedra in $\mathbb R^4$
It is relatively easy to show (see below) that if we have two equilateral triangles of side 1 in $\mathbb R^3$,
such that their union has diameter $1,$ then they must share a vertex.
I wonder whether ...
- 1,359
1
vote
2
answers
1k
views
Is there always a parallelogram cross-section of parallelepiped contained in the smallest box
Let $M$ be a centered parallelepiped, the intersection of $M$ and any plane $P$ that passes through the origin is a parallelogram or hexagon. Each parallelogram or hexagon has a cubic box that is the ...
16
votes
2
answers
1k
views
Are Penrose tilings universal? Do aperiodic universal tilings exist?
Consider a tiling of the plane using tiles of at least two types (e.g, a Penrose tiling such as that shown at the bottom of this question, which tiles the plane with two types of tiles). List the tile ...
- 4,922
52
votes
3
answers
5k
views
Is the "Napkin conjecture" open? (origami)
The falsity of the following conjecture would be a nice counter-intuitive fact.
Given a square sheet of perimeter $P$, when folding it along origami moves, you end up with some polygonal flat figure ...
- 1,306
18
votes
3
answers
2k
views
Are the Platonic solids shadows of 4-polytopes?
Say that a 3D shadow of a 4-polytope is a parallel projection to 3-space, not necessarily orthogonal to that 3-space (that would make it an orthogonal projection).
I am wondering if each of the five ...
- 151k
15
votes
2
answers
2k
views
Partitioning a Rectangle into Congruent Isosceles Triangles
Is it possible to partition any rectangle into congruent isosceles triangles?
- 404
6
votes
1
answer
767
views
Using mirrors to make a non-convex polygon visible from a fixed interior point
Take a point $A$ inside a non-convex polygon $P$. Is it always possible to place a finite set of mirrors given by straight segments (not necessarily along the boundary of $P$, any position inside $P$ ...
- 17.9k
5
votes
3
answers
2k
views
Optimal packing of spheres tangent to a central sphere
Please consider a central, ordinary 2-sphere $S_1$, of some radius $r_1$, and a second ordinary sphere, $S_2$, of radius $r_2$, where $r_2 \leq r_1$.
My question concerns optimal values for the ...
15
votes
3
answers
1k
views
Representation of vectors in $\mathbb{R}^2$ via differences of small vectors.
Is the following fact true?
Let $v_1,\ldots, v_k \in \mathbb{R}^2$, $\|v_i\|\leq 1$, be vectors that add up to zero. Does there exist a permutation $\sigma\in S_k$ and vectors $w_1,\ldots, w_k \...
- 1,284
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 ...
- 151k
7
votes
1
answer
938
views
Which knots' stick numbers are twice their crossing numbers?
Looking at a table of minimum stick numbers for knots (table here),
it seems the known upper bound of $2 c(K)$ in terms of the knot crossing number $c(K)$
is realized by the trefoil $3_1$—it ...
- 151k
16
votes
3
answers
2k
views
A random walk on random lines
I am wondering if this random walk remains finite with positive probability.
Start with three lines $A,B,C$ that are extensions of an equilateral triangle.
Let $p_0$ be one corner. Generate a line $...
- 151k
-1
votes
1
answer
502
views
How to formulate such problem mathematically? (line continuation search) [closed]
I have an array of "lines" each defined by 2 points. I am working with only the line segments lying between those points. I need to search lines that could continue one another (relative to ...
- 13
2
votes
3
answers
8k
views
How many different rectangles (in terms of area) can fit in a 20-unit-wide square?
How many different rectangles (in terms of area) can fit in a 20-unit-wide square? The rectangles can be squares, and their dimensions are integers.
- 103
11
votes
2
answers
1k
views
Which (semi)regular polyhedra are combinations of two others?
The convex combination of convex polytopes is a convex polytope.
An example in $\mathbb{R}^2$ is that a regular octagon
can be obtained as $\frac{1}{2} S + \frac{1}{2} S'$,
where $S$ is a square and $...
- 151k
99
votes
7
answers
20k
views
Can we cover the unit square by these rectangles?
The following question was a research exercise (i.e. an open problem) in R. Graham, D.E. Knuth, and O. Patashnik, "Concrete Mathematics", 1988, chapter 1.
It is easy to show that
$$\sum_{1 \...
- 5,502
1
vote
1
answer
322
views
Settling a circular argument: room for one more?
By using a regular hexagonal arrangement it is simple to fit 19 identical circles into a larger circle of five times the radius with no circles overlapping. This leaves an area equal to six smaller ...
- 13
32
votes
5
answers
2k
views
Nonconvex manhole covers
One common reason given for the circularity of manhole covers is that they can't fall through the manhole. For convex manhole covers, this property is equivalent to having constant width — if ...
- 5,275
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-...
- 935
15
votes
3
answers
1k
views
covering a square with unit squares
Can some square of side length greater than $n$ be covered by $n^2+1$ unit squares? (The unit squares may be rotated. The large square and its interior must be covered.)
- 897
55
votes
6
answers
8k
views
Is it possible to partition $\mathbb R^3$ into unit circles?
Is it possible to partition $\mathbb R^3$ into unit circles?
- 1,414
8
votes
2
answers
741
views
Lattice Stick Number vs. Stick Number of Knot
Can the lattice stick number of a knot be bounded
by the stick number of the knot?
The stick number
$S(K)$ of a knot $K$ is the fewest number of segments
needed to realize it by a simple 3D polygon....
- 151k
8
votes
2
answers
621
views
Generalization of Hamiltonian cycles to "Hamiltonian spheres"
One possible generalization of a Hamiltonian cycle in a triangulated plane graph is what could be
called a Hamiltonian sphere: a collection of triangles within a simplicial complex in $\mathbb{R}^3$
...
- 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
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