All Questions
371 questions
17
votes
2
answers
977
views
Which right square pyramids are scissors congruent to a cube?
Consider a right square pyramid whose base has side length $2r$ and whose height is $h$. Let the dihedral angle between the base and each triangular side be $\theta$, and the dihedral angle between ...
- 2,896
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
16
votes
2
answers
5k
views
Weighted area of a Voronoi cell
Let $X = \{ x_1,\dots,x_n\} $ denote a set of $n$ points in the unit square $S = [0,1]\times[0,1]$, and let $w = \{w_1,\dots,w_n\}$ denote a set of weights corresponding to the $n$ points in $X$. ...
- 195
16
votes
4
answers
1k
views
Squaring a square and discrete Ricci flow
Is this a theorem?
Every $3$-connected planar graph $G$ may be represented as
a tiling of a square by squares,
one square per node of $G$, with nodes connected in $G$
corresponding to tangent squares....
- 151k
16
votes
6
answers
2k
views
Optimal pebble-packing shape
Suppose you throw many ($n$) congruent convex bodies (in $\mathbb{R}^3$) of unit volume (or of unit area in $\mathbb{R}^2$) into a large container, and shake it until little else changes.
Q. ...
- 151k
16
votes
2
answers
951
views
Tiling the square with rectangles of small diagonals
For a given integer $k\ge3$, tile the unit square with $k$ rectangles so that the longest of the rectangles' diagonals be as short as possible. Call such a tiling optimal. The solutions are obvious in ...
- 7,276
16
votes
3
answers
2k
views
Fano plane drawings: embedding PG(2,2) into the real plane
By a drawing of the Fano plane I mean a system of seven simple curves and
seven points in the real plane such that
every point lies on exactly three curves, and every curve contains
exactly three ...
- 23k
16
votes
3
answers
1k
views
Can a convex polytope with $f$ facets have more than $f$ facets when projected into $\mathbb{R}^2$?
Let $P$ be a convex polytope in $\mathbb{R}^d$ with $n$ vertices and $f$ facets.
Let $\text{Proj}(P)$ denote the projection of $P$ into $\mathbb{R}^2$.
Can $\text{Proj}(P)$ have more than $f$ facets?
...
- 163
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
15
votes
3
answers
2k
views
Combinatorial analogues of curvature
There appear to be many "combinatorial" definitions of curvature as applied to finite simplicial (or regular CW) complexes. For instance, we have the ideas of Cheeger, Muller and Schrader, ...
- 15.5k
15
votes
0
answers
477
views
Expanding disks lead to what packing of the plane?
Suppose one sprinkles points uniformly at random on the infinite Euclidean plane,
with some density $\rho$ per unit area.
View the points as disks of radius zero.
Now the radii $r$ of all disks grows ...
- 151k
15
votes
1
answer
640
views
Smallest regular simplex containing the unit cube in $R^n$
What is the length $e_n$ of the edge of the smallest $n$-dimensional regular simplex $S_n$ containing the $n$-dimensional unit cube $Q_n$?
In particular, is there $n$ such that $e_n<\sqrt{2}(n+1-\...
- 6,101
15
votes
1
answer
530
views
Dividing a polyhedron into two similar copies
The paper Dividing a polygon into two similar polygons proves that there are only three families of polygons that are irrep-2-tiles (can be subdivided into similar copies of the original).
Right ...
14
votes
7
answers
2k
views
Finite set of non-collinear points on plane with every point having ≥ 3 equidistant neighbors? [closed]
Does there exist a finite set of points on the Euclidean plane, such that:
No 3 points are collinear, and
Every one of the points has (at least) three other points in the set at the same distance ...
- 169
14
votes
1
answer
781
views
Perimeters of random-walk polygons
I have a random walk on $\mathbb{Z}^2$ that takes a step
with equal probability in the three directions that avoid
retracing the previous step.
The walk proceeds until it returns to a lattice point
...
- 151k
14
votes
1
answer
955
views
Partitioning the vertices of an n-cube with random hyperplane cuts
An evolutionary biologist asked me a question which boils down, at least in part, to what seems to me an interesting question of combinatorial/probabilistic geometry.
It is an old chestnut of a ...
- 19.2k
14
votes
0
answers
416
views
Is the equidissection spectrum closed under addition?
If a polygon can be cut into $m$ as well as into $n$ triangular pieces of equal area, can it also be cut into $m+n$ triangles of equal area?
(I'm editing after realizing that my conjecture that a ...
- 5,492
14
votes
0
answers
479
views
Does every convex polyhedron have a combinatorially isomorphic counterpart whose angles between edges are rational multiples of $\pi$?
After reading these very interesting questions, I came up with another one:
Does every convex polyhedron have a combinatorially isomorphic counterpart whose angles between all pairs of edges meeting ...
- 532
14
votes
3
answers
1k
views
A curious generalization of Helly's theorem
Here is a curious conjectural extension of Helly's theorem.
It may follow (if true) from a useful theorem of the kind asked in this MO question:
Conjecture: Let ${\cal F}=P_1,P_2,\dots,P_m$ be a ...
- 24.7k
13
votes
0
answers
573
views
What are the known convex polyhedra with congruent faces?
Note: I originally asked this question on math.SE here, where I posted a bounty on the question but received no answers after a week despite apparent interest in the problem. I'm hoping MathOverflow ...
- 3,068
13
votes
3
answers
1k
views
Small 4-chromatic coin graphs
A coin graph is a graph that can be represented by a set of disjoint, except possibly touching, unit disks in the plane (i.e. the disks are the vertices and the edges correspond to the pairs that ...
- 143
12
votes
1
answer
474
views
How many subspaces are generated by three or more subspaces in a Hilbert space?
In the book of Garrett Birkhoff "lattice theory", it is mentioned that there are 28 subspaces that can be obtained from three subspaces in general position in a Hilbert space (using ...
- 18.7k
12
votes
3
answers
418
views
'Trapping' 3D regions with sheets of paper
Given a square sheet of paper, how does one create a bag (a closed surface) with it such that the 3D region contained within this closed surface has maximum volume (operations allowed include ...
- 5,979
12
votes
2
answers
2k
views
Distribution of pairwise distances
I am seeking results that describe the distribution of the set of
Euclidean distances between pairs of $n$ points in
a unit square in the plane.
For example: All the distances could be short (a tight ...
- 151k
12
votes
2
answers
642
views
Die-rolling Hamiltonian cycles
Let $R$ be a rectangular region of the integer lattice $\mathbb{Z}^2$,
each of whose unit squares is labeled with a number
in $\lbrace 1, 2, 3, 4, 5, 6 \rbrace$.
Say that such a labeled $R$ is die-...
- 151k
12
votes
2
answers
561
views
Curvature flows for PL closed curves in the plane?
I'm curious to what extent people have studied "curvature flows" on PL closed curves in the plane.
There's a paper by Gage and Hamilton from 1986 that describes the long-term behaviour of smooth ...
- 44.3k
12
votes
2
answers
11k
views
Covering a polygon with rectangles
I am trying to cover a simple concave polygon with a minimum rectangles. My rectangles can be any length, but they have maximum widths, and the polygon will never have an acute angle.
I thought about ...
12
votes
2
answers
2k
views
Fold-and-cut problem in three dimensions
The fold-and-cut theory states that "Any shape with straight sides can be cut from a single (idealized) sheet of paper by folding it flat and making a single straight complete cut. Such shapes include ...
- 851
12
votes
1
answer
765
views
infinite configuration of lines
I was looking at some random problems and questions I liked when I was in high school and I found this one which I still cannot prove.
Does there exist a configuration of a countable number of ...
- 2,035
12
votes
7
answers
683
views
Can a tangle of arcs of ellipses interlock
This is a variation on an earlier question resolved by user35353: Can a tangle of arcs interlock? In that question, the arcs were restricted to circular arcs, and user35353's proof that one arc can be ...
- 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)$ ...
- 151k
12
votes
1
answer
3k
views
Numbers of intersection points and lines
Hello,
I don't know if this question has already been posted, I have made a little search with keywords and did not found it, sorry if I missed anything.
Is it possible to characterize the set of ...
- 449
11
votes
1
answer
607
views
Largest pair of homometric Golomb rulers?
A Golomb ruler is a set of $n$ integers that determines $\binom{n}{2}$ distinct differences.
Two sets are homometric if they determine the same (multiset) of differences.
For example,
$$\{0,1,4,10,12,...
- 151k
11
votes
1
answer
242
views
A variant of Nelson-Hadwiger Problem on the chromatic number of the plane
The famous Nelson-Hadwiger problem asks about the chromatic number of the graph $G$, with the vertex set $V(G)={\mathbb R}^2$ where $a_1=(x_1,y_1), a_2=(x_2,y_2) \in V(G) \ $ form an edge iff $a_1-a_2$...
- 6,214
11
votes
3
answers
1k
views
Combinatorial distance between simplicial complexes
Let $K_1$ and $K_2$ be two simplicial complexes.
I am seeking a measure of the distance between $K_1$ and $K_2$ when
viewed as combinatorial objects.
What I have in mind is something like this.
...
- 151k
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
11
votes
1
answer
442
views
Chromatic number of Voronoi diagrams of lattices
Let $L$ be a Euclidean lattice. Define a graph whose vertex set is $L$ and where two points $x,y\in L$ are declared to be adjacent whenever the cells of $x$ and $y$ in the Voronoi diagram of $L$ have ...
- 32.5k
10
votes
2
answers
280
views
Monochromatic point sets in two-colored plane
Which are the configrations $P\subset \mathbb{R}^2$ of points, such that the following property holds:
Property M (for Monochromatic): Every two-coloring of $\mathbb{R}^2$ contains a monochromatic ...
- 10.7k
10
votes
3
answers
322
views
Integer decomposition property with a partial order
Let $\mathcal{P}$ be a convex lattice polytope in $\mathbb{R}^n$. We say that $\mathcal{P}$ has the integer decomposition property (or "is IDP") if for all $k\in \mathbb{N}$ and $\alpha \in ...
- 24.2k
10
votes
0
answers
609
views
A robust version of Harper's theorem
Let $S$ be subset of $\{0,1\}^n$ with cardinality $k$.
Denote by $\Gamma_r(S)$ the union of all Hamming balls with centers in $S$ and radius $r$.
Harpers's theorem states that $\Gamma_d(S)$ is minimal ...
- 2,576
10
votes
1
answer
426
views
Complexity of the union of randomly rotated unit cubes
It is a remarkable fact that the union of congrent cubes
has only at most near-quadratic combinatorial complexity,
$O^*(n^2)$ for $n$ cubes, known to be almost tight.
This contrasts with the union of ...
- 151k
10
votes
1
answer
411
views
Network flows with capacities on pairs of edges
Take a standard network flow problem: a directed graph with nonnegative capacities on each edge, a source $s$, a sink $t$. We all know how to find the maximum flow from $s$ to $t$.
Now add edge-pair ...
- 37.7k
10
votes
2
answers
547
views
Arbitrarily large finite irreducible matrix groups in odd dimension?
I consider a finite irreducible matrix group $\Gamma\subseteq\mathrm{GL}(\Bbb R^d)$. I am interested in the maximal size of $\Gamma$ depending on $d$. But this question makes only sense if there is an ...
- 13.6k
10
votes
2
answers
3k
views
How do you tell if a system of linear inequalities has a solution?
A naive solution would be to optimize a dummy variable via linear programming and see if a result is returned. I imagine there must be a more direct way.
- 693
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 ...
- 1,090
10
votes
1
answer
3k
views
Computionally efficient vertex enumeration for (convex) polytopes
Let $P \subseteq \mathbb{R}^d$ be an $\mathcal{H}$-polytope. The vertex enumeration problem asks for the set of vertices $V$ of $P$. Theoretically, the vertex enumeration problem for $P$ can be ...
- 321
10
votes
3
answers
500
views
Given the skeleton of an inscribed polytope. If I move the vertices so that no edge increases in length, can the circumradius still get larger?
Let $P\subset \Bbb R^n$ be an inscribed convex polytope, that is, all its vertices are on a common sphere of radius $r$.
Let $G$ be the edge-graph of $P$. For convenience, assume $V(G)=\{1,\dotsc,s\}$....
- 13.6k
9
votes
4
answers
1k
views
Tiling the plane with pairwise non-congruent rational triangles
A rational triangle is one in which all side lengths are rational numbers.
Question: Can we tile the Euclidean plane with rational triangles that are pairwise non-congruent? No further requirements on ...
- 5,979
9
votes
1
answer
2k
views
Uniform sampling from general simplex with a twist
This is part of a question I had asked elsewhere, and then some of the links redirected me to CS stack exchange.
Given $0\leq a_1\leq\dots\leq a_D\leq1$ (all strictly positive), I want to draw points ...
- 221
9
votes
1
answer
295
views
Definition of packing property
Definition 1:
A clutter $C$ is said to have the packing property if $C$ and all of its minors satisfy the König property.
where,
vertex cover of $C$ is a set of vertices that have non-empty ...
- 381