All Questions
Tagged with mg.metric-geometry discrete-geometry
161 questions
49
votes
4
answers
4k
views
What fraction of the integer lattice can be seen from the origin?
Consider the integer lattice points in the positive quadrant $Q$ of $\mathbb{Z}^2$.
Say that a point $(x,y)$ of $Q$ is visible from the origin if the
segment from $(0,0)$ to $(x,y) \in Q$ passes ...
- 151k
8
votes
4
answers
530
views
Inside-out polygonal dissections
A dissection of a polygon $P$
is a partition of $P$ into a finite number of pieces, which can then be rearranged
(via planar translations and rotations) and joined (without overlap) to form a new ...
- 151k
4
votes
2
answers
341
views
Cutting convex regions into equal diameter and equal least width pieces - 2
This post is a spinoff from Cutting convex regions into equal diameter and equal least width pieces
Definitions: The diameter of a convex region is the greatest distance between any pair of points in ...
- 5,979
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
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
51
votes
3
answers
3k
views
Can the sphere be partitioned into small congruent cells?
On the unit $2$-sphere ${\mathbb S}^2$ furnished with the geodesic distance, a subset homeomorphic to a planar disk is called a cell. A finite family of cells is a tiling if their interiors are ...
- 7,276
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 ...
- 151k
30
votes
5
answers
16k
views
How to check if a box fits in a box?
How could I calculate if a rectangular cuboid fits in an other rectangular cuboid, it may rotate or be placed in any way inside the bigger one.
For example would, (650,220,55) fit in (590,290,160), ...
- 429
13
votes
5
answers
1k
views
Packing obtuse vectors in $\mathbb{R}^d$
I came across this attractive theorem:
Theorem. In $\mathbb{R}^d$, there can be at most $d+1$ vectors that
form an obtuse angle with one another.
This was proved1 as a corollary of a lemma about ...
- 151k
4
votes
1
answer
242
views
Shadows and planar sections of polyhedra
By shadow we mean the orthogonal projection of a convex 3D body P onto a 2D plane, for example, the shadow on the xy-plane, with P above (z>0) that plane and the light at L=(0,0,+∞). P an be freely ...
- 5,979
88
votes
2
answers
7k
views
43
votes
12
answers
2k
views
Can a discrete set of the plane of uniform density intersect all large triangles?
Let S be a discrete subset of the Euclidean plane such that the number of points in a large disc is approximately equal to the area of the disc. Does the complement of S necessarily contain triangles ...
- 17.9k
35
votes
3
answers
2k
views
The kissing number of a square, cube, hypercube?
How many nonoverlapping unit squares can (nonoverlappingly) touch one unit square?
By "nonoverlapping" I mean: not sharing an interior point.
By "touch" I mean: sharing a boundary point.
&...
- 151k
17
votes
0
answers
731
views
Does every connected set that is not a line segment cross some dyadic square?
A dyadic square is a subset of $R^2$ of the form $x + 2^{-n} [0,1]^2$ with $x \in 2^{-m} Z^2$, for integers $m,n \geq 0$. We say that a set $A$ crosses a square $S$ if there exists a connected subset ...
- 171
16
votes
3
answers
2k
views
Are infinite planar graphs still 4-colorable?
Imagine you have a finite number of "sites" $S$ in the positive quadrant
of the integer lattice $\mathbb{Z}^2$,
and from each site $s \in S$, one connects $s$ to every lattice point to which it
has a ...
- 151k
12
votes
1
answer
373
views
A claim on partitioning a convex planar region into congruent pieces
Let us define a perfect congruent partition of a planar region $R$ as a partition of it with no portion left over into some finite number n of pieces that are all mutually congruent (ie any piece can ...
- 5,979
9
votes
0
answers
187
views
Cubing the cube - as 'perfectly' as possible
Ref: https://en.wikipedia.org/wiki/Squaring_the_square
A perfect cubing of a cube is a partition of the cube into some finite number of smaller cubes that are pair-wise non-congruent. The above page ...
- 5,979
8
votes
1
answer
2k
views
Lattice points on the boundary of an ellipse
How many points of the integer lattice ${\mathbb Z}^2$ can an axis-parallel ellipse of radius $r$ contain on its boundary? (that is, we consider ${\mathbb Z}^2$ as lying in ${\mathbb R}^2$). ...
- 1,072
8
votes
2
answers
591
views
Cutting a spherical surface into mutually non-congruent pieces of equal area
Question: For what values of integer $n$ can the surface of a sphere be partitioned into $n$ convex and mutually non-congruent pieces of same area? (convexity could be viewed as geodesic convexity). ...
- 5,979
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
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
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
3
votes
0
answers
76
views
A claim on planar sections of 3D convex bodies
Ref: More on shadows of 3D convex bodies,
Shadows and planar sections of polyhedra
Given a 3D convex body C, we define a maximal area (perimeter) section of C with respect to any specified direction $...
- 5,979
2
votes
1
answer
209
views
Cutting convex regions into equal diameter and equal least width pieces
The diameter of a convex region is the greatest distance between any pair of points in the region.
The least width of a 2D convex region can be defined as the least distance between any pair of ...
- 5,979
94
votes
5
answers
9k
views
Is there a dense subset of the real plane with all pairwise distances rational?
I heard the following two questions recently from Carl Mummert, who encouraged me to spread them around. Part of his motivation for the questions was to give the subject of computable model theory ...
- 236k
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
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
36
votes
2
answers
2k
views
Bodies of constant width?
In two-dimensional case one can generalize figures of constant width as figures which can rotate in a convex polygon.
Here is one example which can be used to drill triangular holes:
I would like to ...
- 45k
28
votes
5
answers
2k
views
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$ is an interior point of $P$. Is it true that $X$ can see at least one vertex of $P$? More ...
- 4,484
25
votes
3
answers
994
views
Does every convex polyhedron have a combinatorially isomorphic counterpart whose faces all have rational areas?
Does every convex polyhedron have a combinatorially isomorphic counterpart whose faces all have rational areas?
Does every convex polyhedron have a combinatorially isomorphic counterpart whose edges ...
- 513
17
votes
1
answer
458
views
The sparsest planar net that captures every unit segment
Let $\cal C = \lbrace C_i \rbrace$ be a collection
of rectifiable curves in the plane with the property that
every unit-length segment meets at least one curve
in at least one point.
Call such a ...
- 151k
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
14
votes
3
answers
966
views
Can a tangle of arcs interlock?
Can a (finite) collection of disjoint circle arcs in $\mathbb{R}^3$ be interlocked in the sense in that they cannot be separated, i.e. each moved arbitrarily far from one another while remaining ...
- 151k
14
votes
1
answer
642
views
Which convex bodies can be captured in a knot?
Which convex bodies can be captured in a knot?
This question is based on the discussion in "Is it possible to capture a sphere in a knot?".
We assume that the knot is made from an ...
- 45k
14
votes
2
answers
540
views
Are all well behaved "mean" functions on $\mathbb{R}^+$ equivalent?
Given a set $S$, a function $M: S\times S \rightarrow S$ is a mean if it satisfies the properties:
$M(a,a)=a\qquad$ (identity)
$M(a,b)=M(b,a)\qquad$ (commutativity).
and possibly
$M(M(a,b),M(a,c))=...
- 5,103
13
votes
2
answers
3k
views
How many squares can be formed by using n points?
How many squares can be formed by using n points on a 3 dimensional space?
Like using 4 points, there is 1 square be formed
Using 5 points, still 1 square
Using 6 points, 3 squares can be formed
- 241
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 ...
- 151k
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
13
votes
3
answers
835
views
What fraction of n-point sets in the unit ball have diameter smaller than 1?
This question is inspired by a recent talk by Matt Kahle on random geometric complexes.
Some simple notation: let $\mathcal{B} \subset \mathbb{R}^d$ be the unit ball in $d$-dimensional Euclidean ...
- 15.5k
12
votes
2
answers
5k
views
The Gauss circle problem on a hexagonal lattice
Take an infinite hexagonal lattice (or equivalently, an equilateral triangular lattice), with unit spacing between the closest lattice point pairs, and draw a disc of radius $r$ centered on a lattice ...
- 197
11
votes
1
answer
499
views
Tiling with incommensurate triangles
Say that two triangles are incommensurate if they do not
share an edge length or a vertex angle, and their areas differ.
Suppose you'd like to tile the plane with pairwise incommensurate triangles.
I ...
- 151k
11
votes
1
answer
652
views
How to correctly state Cauchy's rigidity theorem?
Cauchy's rigidity theorem is often stated briefly as
Any two (convex, 3-dimensional) polyhedra with pairwise congruent faces are themselves congruent.
As a more formal generalization to general ...
- 13.6k
10
votes
5
answers
960
views
Is this an instance of any existing convex pentagonal tilings?
Inspired by Wikipedia's article on pentagonal tiling, I made my own attempt.
I believe this belongs to the 4-tile lattice category, because it's composed of pentagons pointing towards 4 different ...
- 151
10
votes
1
answer
465
views
Chord arrangement that avoids confining small or large disks
These two questions are two-dimensional variations on this recent MO question,
"Threading pinholes in the wall of cylinder to pass through an internal coordinate."
Noam Elkies suggested that even a 2D ...
- 151k
8
votes
1
answer
885
views
Maximal tetrahedra inscribed in ellipsoid
Pietro Majer quoted the theorem of Michel Chasles in his MO question,
"Convex curves with many inscribed triangles maximizing perimeter,"
which states that the triangles of maximum perimeter inscribed ...
- 151k
6
votes
1
answer
429
views
Bichromatic pencils
A pencil is a collection of some lines through a point, called the center of the pencil.
If the points of the plane are colored, then call a pencil bichromatic if there is a color that is present on ...
- 18.9k
6
votes
1
answer
470
views
Cutting the unit square into pieces with rational length sides
The following questions seem related to the still open question whether there is a point(s) whose distances from the 4 corners of a unit square are all rational.
To cut a unit square into n (a finite ...
- 5,979
6
votes
1
answer
2k
views
Given a set of 2D vertices, how to create a minimum-area polygon which contains all the given vertices?
Not sure whether this question belongs here or math.stackexchange.
You can assume that all the vertices are unique. The given vertices can be the vertices of the polygon, thus they do NOT have to be ...
- 163
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 ...
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