Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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
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 ...
Joseph O'Rourke's user avatar
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 ...
Nandakumar R's user avatar
  • 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?
Zarathustra's user avatar
  • 1,414
7 votes
1 answer
760 views

Difference Sets

Suppose $$ P \subseteq \{1,2,\dots,N\},\quad |P| = K $$ We calculate the differences as: $$d=p_i-p_j\mod N,\quad i\ne j$$ Now let $a_d$ denote the number of occurrence of $d$ (for $d = 1, 2, \dots , N ...
Mahdi Khosravi's user avatar
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 \...
Kaveh's user avatar
  • 5,502
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
  • 82.6k
69 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
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 ...
Wlodek Kuperberg'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
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), ...
user115086's user avatar
26 votes
3 answers
1k views

Largest possible volume of the convex hull of a curve of unit length

What is the largest possible volume of the convex hull of an open/closed curve of unit length in $\mathbb{R}^3$?
Vladimir Reshetnikov's user avatar
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 ...
Joseph O'Rourke's user avatar
6 votes
2 answers
515 views

On 'fair bisectors' of planar convex regions

Definitions (https://www.ias.ac.in/article/fulltext/pmsc/122/03/0459-0467): Given a planar convex region $C$ (could be smooth or polygonal), an area bisector of $C$ is any line that partitions $C$ ...
Nandakumar R's user avatar
  • 5,979
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 ...
Nandakumar R's user avatar
  • 5,979
143 votes
6 answers
12k 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
88 votes
2 answers
7k views

Light reflecting off Christmas-tree balls

...
Joseph O'Rourke's user avatar
67 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 ...
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
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
41 votes
3 answers
3k 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
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
24 votes
6 answers
3k views

Shortest grid-graph paths with random diagonal shortcuts

Suppose you have a network of edges connecting each integer lattice point in the 2D square grid $[0,n]^2$ to each of its (at most) four neighbors, {N,S,E,W}. Within each of the $n^2$ unit cells of ...
Joseph O'Rourke's user avatar
23 votes
1 answer
954 views

A combinatorial approximation functor sSet->qCat

Let $sSet_J$ denote the category of simplicial sets equipped with the Joyal model structure. Simply by the fact that $sSet_J$ is locally presentable and its class of anodynes ($\neq \mathbf{Cof} \cap ...
Harry Gindi's user avatar
  • 19.6k
18 votes
2 answers
840 views

Reference to a conjecture on unit vectors in Euclidean space

I have heard that there exists the following conjecture (if I am not mistaken). Let $u_1,\dots,u_n$ be unit vectors in an $n$-dimensional Euclidean vector space. Then there exists another unit vector ...
asv's user avatar
  • 21.8k
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 ...
Kevin Johnson's user avatar
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 ...
Joseph O'Rourke's user avatar
12 votes
1 answer
5k views

Closest 3D rotation matrix in the Frobenius norm sense

Given a 3 by 3 matrix $M$ I would like to find the rotation matrix $R$ minimizing the Frobenius norm: \begin{equation} \|R-M\|_F \end{equation} Is there a closed form solution for $R$, or is it ...
Alex Flint's user avatar
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 ...
Nandakumar R's user avatar
  • 5,979
11 votes
3 answers
6k views

Random Sampling a linearly constrained region in n-dimensions...

Hi, So here is my problem: Given a nonlinear, discontinous, cost function $f(x_1,x_2,..,x_N)$ along with linear constraints $x_n \ge 0, \forall n$ $x_n \le c_n$ and $\sum_{n=1}^N x_n = 1$ find an ...
user1's user avatar
  • 113
10 votes
1 answer
1k views

How can we find n points on a plane so that as many pairs of points as possible have the same distance?

There are $n$ points on the plane, and we need to maximize the number of pairs of points which have the same Euclidean distance.
Cynasty's user avatar
  • 159
10 votes
3 answers
2k views

On maximal regular polyhedra inscribed in a regular polyhedron

Let T, C, O, D, or I be regular tetrahedron, cube, octahedron, dodecahedron, and icosahedron, respectively. Suppose that the outer polyhedron have edge-length 1. For example, it's easy to prove that ...
mathlove's user avatar
  • 4,757
10 votes
1 answer
416 views

How are reflection groups related to general point groups?

I always tried to understand how the finite reflection groups of $\Bbb R^d$ (of some fixed dimension $d$) relate to the point groups of the same space $\smash{\Bbb R^d}$ (finite subgroup of the ...
M. Winter's user avatar
  • 13.6k
9 votes
0 answers
186 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 ...
Nandakumar R's user avatar
  • 5,979
8 votes
2 answers
590 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). ...
Nandakumar R's user avatar
  • 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$). ...
Adam Sheffer's user avatar
  • 1,072
6 votes
1 answer
127 views

Convex planar regions with all area bisectors having equal length

Following A claim on the concurrency of area bisectors of planar convex regions, let me record a couple of simple queries. An area bisector (perimeter bisector) of a planar convex region is a chord ...
Nandakumar R's user avatar
  • 5,979
6 votes
6 answers
3k views

Circumference of Convex Shapes

Here is a puzzle I found in Mitteilungen der DMV (roughly, "Letters of the German Society of Mathematicians"), issue 19/2011. It was posed by Alfred Schreiber in "Wie man Hasen fangt" (How to catch ...
Matthias Goergens's user avatar
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 ...
Nandakumar R's user avatar
  • 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 ...
user40780's user avatar
  • 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 ...
M. Winter's user avatar
  • 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 $...
Nandakumar R's user avatar
  • 5,979
3 votes
1 answer
327 views

LP Constraints for Connected Subgraphs of Fixed Size

Question: how can the connectedness-constraint for a subgraph, that is induced by a proper subset $W\subset V$ of the vertices of $G(V,E),\ |V|=n,\ |W|=m$, be formulated in a $LP$ or $ILP$? ...
Manfred Weis's user avatar
  • 13.2k
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 ...
Nandakumar R's user avatar
  • 5,979
1 vote
1 answer
227 views

On comparing planar convex regions of equal perimeter and area

Definitions: The Hausdorff distance between two point sets is the greatest of all the distances from a point in one set to the closest point in the other set. Given two planar convex regions $C_1$ ...
Nandakumar R's user avatar
  • 5,979
1 vote
0 answers
56 views

Bisectors and partitioning lines for convex regions defined with respect to the moment of inertia

Ref: Mathematical Omnibus by Fuchs and Tabachnikov, Lecture 11. Consider any planar convex region C. A line l on the same plane and cutting thru C may be called an inertia bisector of C if it divides ...
Nandakumar R's user avatar
  • 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 ...
Joel David Hamkins'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
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.7k
41 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
  • 3,507

1
2 3 4 5
8