All Questions
Tagged with mg.metric-geometry discrete-geometry
671 questions
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 ...
- 4,713
2
votes
0
answers
69
views
Polygons such that $n^2 $ times magnification of a polygon could be covered by exactly $n^2$ original polygon
While studying about covering problems in combinatorics, I got to a simple question:
What polygons can be covered exactly, without any area that is covered twice or area that is outside the covered ...
- 3,486
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 ...
- 4,713
6
votes
4
answers
2k
views
Delaunay triangulations and convex hulls
This is a reference request.
I have the impression that those who work in computational geometry are accustomed to the following. You have some locally finite set of sites in $\mathbb{R}^n$ and you ...
- 151k
1
vote
1
answer
209
views
Is a polytope with vertices on a sphere and all edges of same length already rigid?
Let's say $P\subset\Bbb R^d$ is some convex polytope with the following two properties:
all vertices are on a common sphere.
all edges are of the same length.
I suspect that such a polytope is ...
- 13.6k
6
votes
1
answer
513
views
The Universality Theorem by Mnev for uniform oriented matroids of rank 4 and higher
According to the Universality Theorem by Mnev (see below theorem 8.6.6 from [1]), for any open semialgebraic variety V there is a uniform oriented matroid of rank 3 whose realization space is stably ...
- 1,482
26
votes
0
answers
359
views
Can 4-space be partitioned into Klein bottles?
It is known that $\mathbb{R}^3$ can be partitioned into disjoint circles,
or into disjoint unit circles, or into congruent copies of a real-analytic curve
(Is it possible to partition $\mathbb R^3$ ...
- 151k
2
votes
1
answer
110
views
A questions concerning Laguerre/Voronoi tessellations
Fix $n>1$ distinguished points $x_1,\ldots, x_n\in \mathbb R^d$, the Voronoi tessellations are the subsets $V_1,\ldots V_n\subset\mathbb R^d$ defined by
$$V_k~~ := ~~ \big\{x\in\mathbb R^d:\quad |...
- 6,337
3
votes
2
answers
344
views
Is a vertex- and edge-transitive polytope already a uniform polytope?
I want to consider (convex) polytopes $P=\mathrm{conv}\{p_1,...,p_n\}\subset\Bbb R^d$ which are both, vertex- and edge-transitive (or maybe stronger: 1-flag-transitive).
Question: Is every such ...
- 13.6k
10
votes
1
answer
623
views
Polyhedron not circumscribed about a sphere
Let $P$ be a polyhedron whose faces are colored black and white so that there are more black faces and no two black faces are adjacent. Show that $P$ is not circumscribed about a sphere.
My teacher ...
- 188k
3
votes
0
answers
142
views
Can bellows make loops?
Can flexible polyhedron (hyperbolic or euclidean) have non-simply connected configuration space not containing singular polyhedra?
- 63.9k
1
vote
1
answer
648
views
How do I find the correct distance spacing for distributing equidistant points on a sphere of a given diameter?
How do I find the correct distance spacing for distributing equidistant points on a sphere of a given diameter?
I don't need to fill the sphere with equidistant points. I just need less than a ...
CommunityBot
- 1
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 ...
- 63.9k
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 ...
- 45k
3
votes
1
answer
553
views
Calculate the discrete set of points B which are in the convex hull of the set of points A
This problem is likely best described with the following picture:
Given the discrete set of points $A$ (shown in blue), I wish to calculate the discrete set of points that are contained within the ...
- 4,713
3
votes
2
answers
323
views
Minimum weight triangulation of lattice points in a circle
Let $r$ be a natural number, and consider the $\mathbb{Z}^2$ lattice points
$S$ inside or on the circle $C$ of radius $r$ centered on the origin.
Let $P$ be the convex hull of $S$; so $P$ is inscribed ...
- 7,276
2
votes
0
answers
98
views
8-partition of a planar convex body by 4 concurrent lines
It is known1 that any convex body $K$ in the plane can be
partitioned into $6$ equal-area pieces by $3$ concurrent lines
which meet at a point in $K$.
Call this a $6$-partition.
This result cannot be ...
- 151k
1
vote
1
answer
230
views
A possible characterization of the cube?
Let $P$ be the $1$-skeleton of a convex polyhedron fixed in $\mathbb{R}^3$,
and $|P|$ the sum of the Euclidean lengths of the edges of $P$.
Let $P_1, P_2, P_3$ be the perpendicular projections of $P$
...
- 4,653
1
vote
0
answers
69
views
Can sufficiently symmetric polytopes be uniquely reconstructed from their 1-skeleton?
General convex polytopes can not be uniquely reconstructed from their 1-skeleton1, as explained here. Not even the dimension is known from the skeleton, as e.g. the complete graph $K_n,n\ge 5$ is the ...
- 4,713
2
votes
1
answer
428
views
Name and Algorithms for a Sparsest Circle Packing
The ordinary circle packing problem in the variant with equal radii asks for the largest radius $r_{max}$ that allows placing $n$ non-overlapping circles with radius $r_{max}$ e.g. in the unit square, ...
CommunityBot
- 1
6
votes
0
answers
1k
views
How to pack 27 $a\times b\times c$ blocks into a cube of side $a+b+c$ with some kind of symmetry?
Recently I stumbled on the problem quoted here about a geometric proof of the AM-GM inequality $$(a_1+\cdots+a_n)^n\ge n^n a_1\cdots a_n$$ by packing $n^n$ rectangular $ n$-dimensional boxes of sides $...
- 13.4k
1
vote
3
answers
229
views
Repeatedly halve and twist a planar shape: Limiting shape?
Consider the following iterative process.
Start with a planar region $R=R_0$ of $\mathbb{R}^2$.
I am thinking of $R$ as connected,
but it may become disconnected.
In the example below, $R$ starts as ...
- 1,100
23
votes
1
answer
524
views
Tying knots via gravity-assisted spaceship trajectories
Q.
Can every knot be realized as the trajectory of a spaceship
weaving among a finite number of fixed planets, subject to gravity alone?
To make this more ...
- 151k
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 ...
- 6,337
49
votes
5
answers
3k
views
If a unitsquare is partitioned into 101 triangles, is the area of one at least 1%?
Update: The answer to the title question is no, as pointed out by Tapio and Willie. I would be more interested in lower bounds.
Monsky's famous theorem with amazingly tricky proof says that if we ...
- 18.9k
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
12
votes
4
answers
2k
views
Longest path through hypercube corners
Is the longest Hamiltonian path through the $2^d$ unit hypercube vertices known,
where path length is measured by Euclidean distance in $\mathbb{R}^d$?
The unit hypercube spans from $(0,0,\ldots,0)$ ...
- 1,042
3
votes
1
answer
118
views
Question arise from kissing number in 2 dimension
I'm considering an extended problem of kissing number in $\mathbb{R}^2$.
Suppose I have a given disc $\mathcal{D}$ of radius 1/2 and infinitely many discs all of radius 1/2 and all these discs and ...
- 39.9k
3
votes
1
answer
205
views
How to show it is contained in a convex hull?
There are $(d+1)f$ points (denote the set of all points as $S$) in $\mathbb{R}^d$, that can be divide into $d+1$ disjoint sets $F_1,...,F_{d+1}$, each set of size $f$. If we have
$$
\mathcal{H}(F_i)\...
6
votes
0
answers
164
views
Sets of points avoiding small angles
(1) $\mathbb{R}^2$.
I'd like to place $n$ points in the plane so that the smallest angle they
determine is as large as possible.
In a sense, such a point set is in very general position, not only
...
- 151k
3
votes
1
answer
206
views
Separating points of shifts of a finite set in the plane
Let $A\subset \mathbb{R^2}$ be a finite set such that $|A|=k^2$. Let $x_i\in \mathbb{R^2}$, $i=1,2,3,4$, be four points in the plane in general position (no three lie on any line).
Let us form the ...
- 23k
1
vote
0
answers
196
views
Squares as sum of squares
For which positive integers n is $n^2$ the sum of precisely n smaller positive squares?
Of these n x n squares, which can be actually cut into n smaller squares?
- 3,707
3
votes
0
answers
351
views
Properties of inverse Cayley-Menger matrices
in the online article A formula for the N-circumsphere of an N-simplex dated April 2013, G. Westendorp provides an interpretation of the entries of inverse of Cayley-Menger matrices $\hat{B}$, that ...
- 13.2k
3
votes
0
answers
214
views
Volume of intersection of a ball and cube with arbitrary position in $n$ dimension
Let $ A(n, r, x) = B^n_r(x) \cap [0,1]^n $ denote the intersection between an $n$ ball $B^n_r(x)$ with arbitrary radius $r$ and arbitrary center $x \in \mathbb{R}^n$ that intersects a unit $n$ cube $ [...
- 63.9k
10
votes
1
answer
9k
views
Get Largest Inscribed Rectangle of a Concave Polygon
I'm looking for an algorithm to find a set of largest inscribed rectangles of a concave polygon where each rectangle must be collinear with one of the edges of the polygon.
In other words, I want to ...
- 4,713
6
votes
1
answer
450
views
Dissecting a tetrahedron into orthoschemes
Is there a way to dissect any tetrahedron into a finite number of orthoschemes?
I know that for a tetrahedron which only has acute angles, one can take the center of the inscribed circle and project ...
- 4,713
6
votes
1
answer
508
views
How many triangulations of a regular octahedron are there, without introducing new vertices?
It is easy to find three triangulations, each consisting of four tetrahedra. Are there more?
- 156k
13
votes
1
answer
3k
views
What nets fold to polyhedra?
There is a classic (and open) problem asking whether every polyhedron can be unfolded to give a non-overlapping net. The converse problem has been studied asking which polygons can be folded in some ...
CommunityBot
- 1
17
votes
5
answers
883
views
Rigidity of convex polyhedrons in $\mathbb R^3$ with faces removed
Take a convex polyhedron $P$ in $\mathbb R^3$ and remove all the faces, i.e. leave only the edges. Call this graph $E$. Let us now try to continuously deform $E$ in $\mathbb R^3$ so that all the edges ...
- 14.3k
11
votes
2
answers
455
views
Dodecahedral rolling distance
Let a dodecahedron sit on the plane,
with one face's vertices on an origin-centered unit circle.
Fix the orientation so that the edge whose indices are $(1,2)$ is horizontal.
For any $p \in \mathbb{R}...
- 151k
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 ...
- 1,228
7
votes
0
answers
209
views
Stabbing disks in space, or: Galactic alignment
I have a collection of $n$ unit-radius disks in $\mathbb{R}^3$, whose centers are
random within a sphere of radius $R>1$, and which are each oriented randomly.
I'd like to find a line $L$ that ...
CommunityBot
- 1
10
votes
5
answers
834
views
Tessellating $\mathbb{R}^n$ by bricks.
Let us call the $\ell_1$-product of intervals $[0,k_1]\times...\times [0,k_n]$ a brick of size $k_1+...+k_n$. Consider a tessellation $T$ of $\mathbb{R^n}$ by (shifted) bricks so that every point ...
- 61.9k
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 $...
- 1,228
22
votes
4
answers
2k
views
Non-chaotic bouncing-ball curves
I was surprised to learn from two
Mathematica Demos by
Enrique Zeleny that an elastic ball bouncing in a V or in a sinusoidal channel
exhibits chaotic behavior:
(The Poincaré map ...
CommunityBot
- 1
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,713
11
votes
1
answer
406
views
Thinnest 2-fold coverings of the plane by congruent convex shapes
It is an unsolved problem to determine the "thinnest" $2$-fold covering of
the plane by disks.
The $2$-fold coverage problem by disks is to find the minimum number of congruent
(unit-radius) disks ...
- 151k
10
votes
3
answers
537
views
Perimeter-halving center of a convex shape
Let $P$ be a convex polygon (or any convex body in $\mathbb{R}^2$)
with perimeter of length $1$. Call a chord $c$ of $P$ perimeter-halving
if half the perimeter lies to one side of $c$
(and so half to ...
- 151k
9
votes
1
answer
2k
views
Billiard dynamics with angle of reflection a fraction of angle of incidence
Suppose that a billiard ball bouncing in a unit square (or a lightray reflecting
in a mirrored square) has the property that the angle of reflection is a fraction
of the angle of incidence, rather ...
- 151k
21
votes
2
answers
1k
views
On convergence of convex bodies
Let $K\subset \mathbb{R}^n$ be a compact convex set of full dimension. Assume that $0\in \partial K$.
Question 1. Is it true that there exists $\varepsilon_0>0$ such that for any $0<\...
- 7,194