The combinatorial-geometry tag has no wiki summary.

**55**

votes

**5**answers

2k 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 ...

**53**

votes

**1**answer

2k 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 ...

**45**

votes

**2**answers

2k 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 ...

**31**

votes

**0**answers

441 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$} ...

**30**

votes

**4**answers

1k 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 sidelength, then the tiled rectangle $R$ has at least one integer side length.
...

**27**

votes

**3**answers

2k views

### Is the ratio Perimeter/Area for a finite union of unit squares at most 4?

Update: As I have just learned, this is called Keleti's perimeter area conjecture.
Prove that if H is the union of a finite number of unit squares in the plane, then the ratio of the perimeter and ...

**26**

votes

**2**answers

847 views

### Bodies of constant width?

In two-dimensional case one can generalize figures of constant width as figures which can rotate in a covex polygon.
Here is one example which can be used to drill triangular holes:
I would like to ...

**26**

votes

**2**answers

604 views

### Careless packing

The sequence $\frac{1}{2}, \frac{1}{2\cdot 2}, \frac{1}{3\cdot 4}, \frac{1}{4\cdot 6}, \frac{1}{5\cdot 8}, \frac{1}{6\cdot 10},\ldots$ has a curious property, as follows:
a) the series with these ...

**24**

votes

**3**answers

1k 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$ ...

**22**

votes

**3**answers

2k views

### Covering a circle with red and blue arcs

We have a circle and two families of $n$ red arcs and $n$ blue arcs, positioned on the circle so that every two arcs of different colors intersect. Can one show that there is a point in the perimeter ...

**22**

votes

**2**answers

932 views

### A geometric Ramsey problem

The following problem seems like one to which the answer could well be known: if so, I'd be interested to have a reference.
How large does n have to be such that among any n points in the plane you ...

**20**

votes

**1**answer

632 views

### Sane bound on number of moves for Maker-Breaker game on $\mathbb R^2$ for $\{0,1,2,3,4\}$

The description below comes from
József Beck. Combinatorial games. Tic-tac-toe theory, Encyclopedia of Mathematics and its Applications, 114. Cambridge University Press, Cambridge, 2008, MR2402857 ...

**19**

votes

**3**answers

715 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 ...

**19**

votes

**3**answers

4k views

### Cutting a rectangle into an odd number of congruent pieces

We are interested in tiling a rectangle with copies of single tile (rotations and reflexions are allowed). This is very easy to do, by cutting the rectangle into smaller rectangles.
What happens when ...

**19**

votes

**8**answers

1k views

### Higher-dimensional Catalan numbers?

One could imagine defining various notions of higher-dimensional Catalan numbers,
by generalizing objects they count.
For example, because the Catalan numbers count the triangulations of convex ...

**19**

votes

**1**answer

452 views

### Voronoi cell of lattices with the same profile

Definition 1. Given a body $V$ in $\mathbb R^n$,
the function $p_V\colon \mathbb R_+\to \mathbb R_+$
$$p_V(r)=\mathop{\rm vol} [V\cap B_r(0)]$$
will be called profile of $V$.
Definition 2. Define ...

**17**

votes

**1**answer

449 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$?

**16**

votes

**0**answers

459 views

### Monomer-Dimer tatami tilings need better relationships with other math. Summary of results.

A monomer-dimer tiling of a rectangular grid with $r$ rows and $c$ columns satisfies the \emph{tatami} condition if no four tiles meet at any point. (or you can think of it as the removal of a ...

**15**

votes

**3**answers

966 views

### Is Euler characteristic of a simplicial complex upper bounded by a polynomial in the number of its facets ?

What is the best upper bound known on the (absolute value of) the
Euler characteristic of a simplicial complex
in terms of the number of its facets ?
In particular, I am interested in proving or ...

**15**

votes

**2**answers

293 views

### Integer lattice points on a hypersphere

Is the following statement true?
For every integer $n\ge2$ and every integer $k\ge0$ there exists a hypersphere in $\mathbb{R}^n$ (circle, sphere etc) containing exactly $k$ integer lattice ...

**15**

votes

**4**answers

2k views

### Why is complex projective space triangulable?

In an exercise in his algebraic topology book, Munkres asserts that $\mathbf{C}P^n$ is triangulable (i.e., there is a simplicial complex $K$ and a homeomorphism $|K| \rightarrow \mathbf{C}P^n$). Can ...

**15**

votes

**1**answer

323 views

### Does every convex polyhedron have a combinatorially isomorphic counterpart whose all faces 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 ...

**14**

votes

**3**answers

1k views

### Representation of vectors in $\mathbb{R}^2$ via differences of small vectors.

Is the following fact true?
Let $v_1,\ldots, v_k \in \mathbb{R}^2$, $\|v_i\|\leq 1$, be vectors that add up to zero. Does there exist a permutation $\sigma\in S_k$ and vectors $w_1,\ldots, w_k ...

**13**

votes

**2**answers

1k views

### How many vertices/edges/faces at most for a convex polyhedron that tiles space?

I wonder if this problem has already been examined before:
Consider a convex polyhedron that tiles $\mathbb R^3$. What is the maximum of vertices/edges/faces that such a polyhedron can have?
...

**13**

votes

**1**answer

470 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 ...

**13**

votes

**0**answers

1k views

### Minimum tiling of a rectangle by squares

Given the $n\times m$ rectangle, I want to compute the minimum number of integer-sided squares needed to tile it (possibly of different sizes).
Is there an efficient way to calculate this?

**12**

votes

**2**answers

219 views

### Smallest containing simplex

Let $V_n$ be the least real number such that for every convex subset of $\mathbb{R}^n$ with hypervolume $1$ there is a containing simplex with hypervolume $V_n$.
What is known about $V_n$? Is there a ...

**12**

votes

**3**answers

473 views

### Is {6,3,7} an 'ultrahyperbolic' Coxeter group?

These pictures, drawn by Roice Nelson, are attempts to visualize a geometry having as symmetries the {6,3,7} Coxeter group, by which I mean the one coming from the Coxeter diagram
...

**11**

votes

**2**answers

704 views

### Access to a preprint by D. N. Verma

Some work I am doing is connected with a sequence 1, 3, 40, 1225, 67956, $\dots$ which agrees with http://oeis.org/A012250 for all eight terms. The only useful information in OEIS on this sequence is ...

**11**

votes

**3**answers

373 views

### Is there a nice way to “unravel” a great dodecahedron?

The great dodecahedron is a non-convex regular polyhedron bounded by 12 pentagonal faces, crossing each other, arranged in a star-shaped manner around each of its 12 vertices (see the Wikipedia page ...

**11**

votes

**2**answers

270 views

### When does a set of collinearity conditions imply collinearity of all of the points?

Suppose we have a set of $n$ points $\{X_1,X_2,\dots,X_n\}$ in the real plane and $\mathcal{A}$ a family of subsets of $\{1,\dots,n\}$.
By a "set of collinearity conditions for $\mathcal{A}$" we mean ...

**11**

votes

**3**answers

1k views

### When are Ehrhart functions of compact convex sets polynomials?

Given a lattice $L$ and a subset $P\subset \mathbb R^d$, we define for each positive integer $t$ $$f_P(L,t)=|(tP\cap L)|$$ the number of lattice points in $tP$. Let's say $P$ is nice if $f_P(L,t)$ is ...

**11**

votes

**2**answers

604 views

### Drawing 3-configurations of points and lines with straight lines

It is well-known that the black-and-white coloring of the Heawood graph on 14 vertices determines a combinatorial 3-configuration with 7 "points" and 7 "lines", known as Fano plane. Similarly, any ...

**11**

votes

**0**answers

375 views

### Hrushovski's Construction

Zilber expressed a conjecture for $\aleph_{1}$- categorical theories.(In 80s)
Zilber's Conjecture: The geometry of any $\aleph_{1}$- categorical structure is one of the following:
a) Trivial (No ...

**11**

votes

**0**answers

356 views

### Reciprocity (Ehrhart-style) for real polytopes?

Is there some sense in which the well-known Ehrhart reciprocity law for rational, convex, polytopes can be extended to any convex polytope with arbitrary real vertices?
In other words, given any ...

**10**

votes

**1**answer

304 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 ...

**10**

votes

**2**answers

1k views

### Subdivision of triangles into congruent triangles

Recently some old notes of mine have gotten me to thinking about the problem of subdividing a triangle into $N$ smaller triangles, all congruent to one another. A little thought shows the following ...

**10**

votes

**3**answers

586 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, of Forman ...

**10**

votes

**1**answer

384 views

### Random geometric graphs and spanners

I would grateful to learn of work mixing
random geometric graphs with random graphs under
the
Erdős-Renyi model, and in particular concerning spanners.
Select $n$ points uniformly at random from the ...

**9**

votes

**3**answers

705 views

### Polytopes with few vertices.

Suppose I have a convex polytope in $\mathbb{R}^d$ which I know has few vertices (in the case which prompted this question, I seem to have a polytope in $\mathbb{R}^9$ which has sixteen vertices). Is ...

**9**

votes

**3**answers

689 views

### Point sets in Euclidean space with a small number of distinct distances

It is well known and not hard to prove that the regular simplex in n-dimensions is the only way to place n+1 points so that the distance between distinct pairs of points is always the same. My general ...

**9**

votes

**1**answer

233 views

### Which values can attain the minimum solid angle in a simplex

Given a simplex $S$ with a vertex $v$ by the solid angle at this vertex I mean the value $\hbox{vol}(B \cap S)/\hbox{vol}(B)$ where $B$ is a small enough ball centered at $v$ (for example, in the ...

**9**

votes

**2**answers

327 views

### On well separated point sets in the plane

Let us say that a finite set $A$ in the plane is $1$-separated if:
1) it has an even number of points;
2) no open ball of diameter $1$ contains more than $|A|/2$ points.
For a $1$-separated set $A$ ...

**9**

votes

**2**answers

282 views

### The area of the intersection of convex sets with prescribed pairwise intersections

Consider two numbers $a>b>0$. Let $A_1,A_2,A_3$ be three convex sets in ${\mathbb R}^2$ such that $\mu(A_i)=a$, $\mu(A_i\cap A_j)=b$ ($\mu$ is the usual measure on ${\mathbb R}^2$). What is the ...

**9**

votes

**1**answer

265 views

### Maximum number of Vertices of Hypercube covered by Ball of radius R

Let $R>0$ be given and let $H^n$ be the unit hypercube in $\mathbb{R}^n$. The problem I am facing is to find the maximum number of vertices of $H^n$ which can be covered by a closed $n$-dimensional ...

**8**

votes

**7**answers

760 views

### Omniscient bots gathering on $\mathbb{Z}^2$

There are $N=n^2$ "bots" on distinct integer lattice points in the plane.
Each knows the positions $p_i$ of all bots, and each has unlimited (private) memory.
Each executes the same algorithm ...

**8**

votes

**3**answers

898 views

### Which finite groups are generated by n involutions?

One of the interesting problems in abstract polytope theory is to determine, for a given finite group, when that group is the automorphism group of a regular abstract polytope. This is equivalent to ...

**8**

votes

**2**answers

550 views

### A Problem about partitioning $S^2$

Question: Can the 2-dimensional sphere $S^2$ be partitioned into four nonempty sets such that every circle in $S^2$ passes through just three of these four sets?
Here, "just three" means "exactly ...

**8**

votes

**2**answers

651 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 ...

**8**

votes

**0**answers

296 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 ...