Questions tagged [discrete-geometry]

Finite or discrete collections of geometric objects. Packings, tilings, polyhedra, polytopes, intersection, arrangements, rigidity.

Filter by
Sorted by
Tagged with
142 votes
6 answers
11k views

Gaussian prime spirals

Imagine a particle in the complex plane, starting at $c_0$, a Gaussian integer, moving initially $\pm$ in the horizontal or vertical directions. When it hits a Gaussian prime, it turns left $90^\circ$...
Joseph O'Rourke's user avatar
96 votes
7 answers
19k 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 \...
Kaveh's user avatar
  • 5,362
93 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 ...
Joel David Hamkins's user avatar
92 votes
5 answers
4k views

Can a row of five equilateral triangles tile a big equilateral triangle?

Can rotations and translations of this shape perfectly tile some equilateral triangle? I originally asked this on math.stackexchange where it was well received and we made some good progress. Here's ...
Oscar Cunningham's user avatar
86 votes
2 answers
6k views

Light reflecting off Christmas-tree balls

...
Joseph O'Rourke's user avatar
79 votes
6 answers
4k views

Does every polyomino tile R^n for some n?

This is a question posed by Adam Chalcraft. I am posting it here because I think it deserves wider circulation, and because maybe someone already knows the answer. A polyomino is usually defined to ...
Timothy Chow's user avatar
  • 78.1k
68 votes
3 answers
9k views

What is the status of the Gauss Circle Problem?

For $r > 0$, let $L(r) = \# \{ (x,y) \in \mathbb{Z}^2 \ | \ x^2 + y^2 \leq r^2\}$ be the number of lattice points lying on or inside the standard circle of radius $r$. It is easy to see that $L(r) ...
Pete L. Clark's user avatar
67 votes
3 answers
11k views

Nonconvexity and discretization

Edit: Here's a more down-to-earth, and somewhat weakened, but I believe still nontrivial, version of the main theorem. Prototypical nonconvex spaces are $\ell^p$-spaces for $0<p<1$, say $\ell^p(\...
Peter Scholze's user avatar
65 votes
22 answers
10k views

When has discrete understanding preceded continuous?

From my limited perspective, it appears that the understanding of a mathematical phenomenon has usually been achieved, historically, in a continuous setting before it was fully explored in a discrete ...
65 votes
3 answers
3k views

How many unit cylinders can touch a unit ball?

What is the maximum number $k$ of unit radius, infinitely long cylinders with mutually disjoint interiors that can touch a unit ball? By a cylinder I mean a set congruent to the Cartesian product of ...
Wlodek Kuperberg's user avatar
65 votes
2 answers
4k views

How many cubes cover a bigger cube?

How many $n$-dimensional unit cubes are needed to cover a cube with side lengths $1+\epsilon$ for some $\epsilon>0$? For n=1, the answer is obviously two. For n=2, the drawing below shows that ...
J.C. Ottem's user avatar
  • 11.5k
55 votes
6 answers
7k views

Is it possible to partition $\mathbb R^3$ into unit circles?

Is it possible to partition $\mathbb R^3$ into unit circles?
Zarathustra's user avatar
  • 1,404
55 votes
5 answers
2k views

Do unit quaternions at vertices of a regular 4-simplex, one being 1, generate a free group?

Choose unit quaternions $q_0, q_1, q_2, q_3, q_4$ that form the vertices of a regular 4-simplex in the quaternions. Assume $q_0 = 1$. Let the other four generate a group via quaternion ...
John Baez's user avatar
  • 21.3k
54 votes
5 answers
4k views

Can an arbitrary collection of circles of total area 1/2 fit into a circle of area 1?

Assume the circles are actually open disks, otherwise two circles each of area $\frac{1}{4}$ wouldn't fit into the circle of area 1. This seems like it should be true, thinking about packing density,...
Henry Segerman's user avatar
52 votes
5 answers
8k views

Why do bees create hexagonal cells ? (Mathematical reasons)

Question 0 Are there any mathematical phenomena which are related to the form of honeycomb cells? Question 1 Maybe hexagonal lattices satisfy certain optimality condition(s) which are related to it? ...
Alexander Chervov's user avatar
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 ...
Jérôme JEAN-CHARLES's user avatar
52 votes
5 answers
2k views

Tetris-like falling sticky disks

Suppose unit-radius disks fall vertically from $y=+\infty$, one by one, and create a random jumble of disks above the $x$-axis. When a falling disk hits another, it stops and sticks there. Otherwise, ...
Joseph O'Rourke's user avatar
51 votes
3 answers
2k 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 ...
Wlodek Kuperberg's user avatar
51 votes
4 answers
6k views

what-if.xkcd.com: stabbing (simply connected) regions on the 2-sphere with few geodesics

In the latest what-if Randall Munroe ask for the smallest number of geodesics that intersect all regions of a map. The following shows that five paths of satellites suffice to cover the 50 states of ...
Moritz Firsching's user avatar
51 votes
2 answers
3k views

vector balancing problem

I believe the solution posted to the arXiv on June 17 by Marcus, Spielman, and Srivastava is correct. This problem may be hard, so I don't expect an off-the-cuff solution. But can anyone suggest ...
Nik Weaver's user avatar
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 ...
Joseph O'Rourke's user avatar
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 ...
domotorp's user avatar
  • 18.3k
48 votes
8 answers
5k views

A sudden smiley? :-)

This is a vague question, and I will no doubt be (properly!) chastised for posing it. I would like to generate a set $S$ of points in $\mathbb{R}^3$—$|S|$ finite or infinite—which has the ...
Joseph O'Rourke's user avatar
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 ...
filipm's user avatar
  • 1,359
45 votes
0 answers
909 views

Extending a line-arrangement so that the bounded components of its complement are triangles

Given a finite collection of lines $L_1,\dots,L_m$ in ${\bf{R}}^2$, let $R_1,\dots,R_n$ be the connected components of ${\bf{R}}^2 \setminus (L_1 \cup \dots \cup L_m)$, and say that $\{L_1,\dots,L_m\}...
James Propp's user avatar
  • 19.4k
44 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 ...
Joseph O'Rourke's user avatar
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 ...
Roland Bacher's user avatar
43 votes
0 answers
1k views

Can a regular icosahedron contain a rational point on each face?

The title says it all: Is there a (regular) icosahedron containing a rational point on each of its faces? For other Platonic solids, the affirmative answer is easy. Indeed, regular tetrahedra, cubes, ...
Ilya Bogdanov's user avatar
42 votes
2 answers
2k views

Does any set of dominoes tile some common figure?

Let $D_1,\dots,D_n \subset \mathbb{Z}^2$ be two-point sets, i.e. 'dominoes' (unlike common dominoes, these are not necessarily connected, but I couldn't come up with a better name). Does there always ...
Arsenii Sagdeev's user avatar
41 votes
3 answers
3k views

Can one recover the smooth Gauss Bonnet theorem from the combinatorial Gauss Bonnet theorem as an appropriate limit?

First let me state two known theorems. Theorem 1 (for smooth manifolds): Let $(M,g)$ be a smooth compact two dimensional Riemannian manifold. Then $$ \int \frac{K}{2 \pi} dA = \chi (M) $$ where $K$ ...
Ritwik's user avatar
  • 3,235
41 votes
2 answers
2k views

Can we find lattice polyhedra with faces of area 1,2,3,...?

I asked this question two months ago on MSE, where it earned the rare Tumbleweed badge for garnering zero votes, zero answers, and 25 views over 61 days. Perhaps justifiably so! Here I repeat it with ...
Joseph O'Rourke's user avatar
40 votes
2 answers
3k views

Conjecture: If circular coins of any sizes are in a convex polygonal frame, with each coin touching exactly one edge, then all the coins can move

Suppose some circular coins (not necessarily the same size) are in a frame. The coins may be immobile, as in this example: On the other hand, they may be free to move, as in these examples (in which ...
Dan's user avatar
  • 2,341
40 votes
1 answer
1k views

Four circles on the sphere

Consider generic configurations consisting of 4 distinct circles on the sphere. Two configurations are equivalent if they can be mapped onto each other by a homeomorphism of the sphere. How to ...
Alexandre Eremenko's user avatar
38 votes
3 answers
2k views

Is there a regular pentagon with a rational point on each edge?

This question was asked by Yaakov Baruch in the comments to the question Can a regular icosahedron contain a rational point on each face? It seems that this question deserves special attention.
Alexey Ustinov's user avatar
38 votes
7 answers
5k views

Shortest path connecting two opposite points on a cube

Is it true, that a path connecting two opposite points (i.e. such that the segment joining them passes through the centre of mass of the cube) on the surface of the $d$-dimensional unit cube (with $d&...
Arseniy Akopyan's user avatar
37 votes
2 answers
2k views

Can the unsolvability of quintics be seen in the geometry of the icosahedron?

Q1. Is it possible to somehow "see" the unsolvability of quintic polynomials in the $A_5$ symmetries of the icosahedron (or dodecahedron)? Perhaps this is too vague a question. Q2. Are there ...
Joseph O'Rourke's user avatar
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 ...
Anton Petrunin's user avatar
36 votes
0 answers
1k views

3-colorings of the unit distance graph of $\Bbb R^3$

Let $\Gamma$ be the unit distance graph of $\Bbb R^3$: points $(x,y)$ form an edge if $|x,y|=1$. Let $(A,B,C,D)$ be a unit side rhombus in the plane, with a transcendental diagonal, e.g. $A = (\alpha,...
Igor Pak's user avatar
  • 16.3k
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.   &...
Joseph O'Rourke's user avatar
35 votes
4 answers
2k views

Tiling a rectangle with a hint of magic

Here's a a famous problem: If a rectangle $R$ is tiled by rectangles $T_i$ each of which has at least one integer side length, then the tiled rectangle $R$ has at least one integer side length. There ...
Alex R.'s user avatar
  • 4,902
35 votes
2 answers
2k views

What is the oriented Fano plane?

One way to remember the multiplication table of the octonions is to use the following diagram (which I got from John Baez's online paper): if $(e_i,e_j,e_k)$ is one of the lines listed according to ...
Mariano Suárez-Álvarez's user avatar
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 ...
Joseph O'Rourke's user avatar
33 votes
1 answer
2k views

Is there a configuration of 5 points on the plane where any two can be covered by an axis aligned rectangle?

I'm trying to figure out the question in the title for a project that I'm working on. My goal is to find a configuration of five integer points on the plane, where we can overlap any pair of them ...
aradarbel10's user avatar
33 votes
3 answers
5k views

Do bubbles between plates approximate Voronoi diagrams?

For example, soap bubbles:                   Image from UPenn: "A 2-dimensional foam of wet soap bubbles squashed between glass plates, after 10 hours ...
Joseph O'Rourke's user avatar
33 votes
4 answers
2k views

How many random walk steps until the path self-intersects?

Take a random walk in the plane from the origin, each step of unit length in a uniformly random direction. Q. How many steps on average until the path self-intersects? My simulations suggest ~$8....
Joseph O'Rourke's user avatar
33 votes
3 answers
2k views

chromatic number of the hyperbolic plane

A notorious problem in combinatorics is the following: If we color $\mathbb{R}^2$ so that no pair of points at unit distance get the same color, what is the fewest number of colors required? This ...
Matthew Kahle's user avatar
33 votes
1 answer
3k views

Tiling a square with rectangles

Is it possible to completely tile a square with different rectangles of integer sides but all with the same area? The original problem, not requiring integer sides for rectangles, was proposed by Joe ...
Bernardo Recamán Santos's user avatar
32 votes
5 answers
1k views

Can every $\mathbb{Z}^2$ disk be pinball-reached?

Let every point of $\mathbb{Z}^2$ be surrounded by a mirrored disk of radius $r < \frac{1}{2}$, except leave the origin $(0,0)$ unoccupied by a disk. Q. Is it the case that every disk can be hit ...
Joseph O'Rourke's user avatar
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 ...
Richard Dore's user avatar
  • 5,205

1
2 3 4 5
37