Combinatorial geometry is concerned with combinatorial properties and constructive methods of discrete geometric objects. Questions on this topic are on packing, covering, coloring, folding, symmetry, tiling, partitioning, decomposition, and illumination problems.

learn more… | top users | synonyms

69
votes
1answer
4k views

Gerrymandering on a high-genus surface/can I use my powers for evil?

Somewhat in contrast to this question. Let's say the Supreme Court has just issued a ruling that the upper and lower roads of an overpass need not be in the same congressional district. This makes ...
39
votes
3answers
3k views

Cutting up a circle to make a square

We know that there is no paper-and-scissors solution to Tarski's circle-squaring problem (my six-year-old daughter told me this while eating lunch one day) but what are the closest approximations, if ...
26
votes
3answers
611 views

Expected length of the shortest polygonal path connecting random points

$N$ points are selected in a uniformly distributed random way in a disk of a unit radius. Let $L(N)$ denote the expected length of the shortest polygonal path that visits each of the points at least ...
26
votes
4answers
609 views

square cake with raisins

Alice bakes a square cake, with $n$ raisins (= points). Bob cuts $p$ square pieces. They are axis-aligned, interior-disjoint, and each piece must contain at least $2$ raisins. Note that a single ...
22
votes
1answer
507 views

How many balls of radius 1 can be packed into a sphere of radius 10?

How I can calculate the maximum number of balls of radius 1 that can be packed into a sphere of radius 10?
21
votes
3answers
395 views

Maximum $C$ such that every shape in $\Bbb R^2$ with area $<C$ can be placed to avoid $\Bbb Z^2$

For $C=1$, it has been proved here that every shape in the plane having area less than $1$ can be translated and rotated so that it does not touch any element of $\mathbb Z^2$. (In fact, for $C=1$, ...
19
votes
0answers
386 views

Can Three Equilateral Triangles with Sidelength $s$ Cover A Unit Square?

A previous question on the site asked for a short proof of the fact that three equilateral triangles with unit side length cannot be arranged to cover a square with unit side lengths. Given the truth ...
19
votes
0answers
241 views

Geometric way to view the truncated braid groups?

This is perhaps a vague question, but hopefully there exists literature on the subject. The question is motivated by an answer I gave to this question. I also asked a related question on MO, although ...
17
votes
2answers
341 views

5 moving points in plane, one goes to infinity

Suppose we have $5$ points in plane, each lying on a line for which no three of these lines intersect in one point, and also non of these $5$ points is an intersection point of two lines. At time ...
17
votes
1answer
231 views

How many planar arrangements of $n$ circles?

Is there a known formula or recursion for the number of distinct arrangements of $n$ distinct circles in a plane, where two arrangements are regarded as distinct unless one can be obtained from the ...
16
votes
1answer
776 views

How many different shapes can I make with this toy?

I have the following toy, perhaps some of you have seen it before. It consists of a bunch of cubes with an elastic string in the middle. You can bend it into different shapes like this: Or this: ...
15
votes
1answer
239 views

Hypercube and Hyperspheres

Let $n,k\in\mathbb{N}$. In this problem, the geometry of $\mathbb{R}^n$ is the usual Euclidean geometry. The lattice hypercube $ Q(n,k)$ is defined to be the set $ \{1,2,...,k\}^n ...
14
votes
4answers
474 views

If any triangle has area at most 1 , points can be covered by a rectangle of area 2.

I am working on this problem for some time, and I am not able to finish the argument: There is a finite number of points in the plane, such that every triangle has area at most 1. Prove that the ...
14
votes
2answers
577 views

Two cubes in unit cube

A cube of side one contains two cubes of sides $a$ and $b$ having non-overlapping interiors. How to prove the inequality $a+b \le 1?$ The same question in higher dimensions.
13
votes
1answer
354 views

Packing an infinite sequence of disks

Let $a > 1$ and $Q(a)$ denote the supremum of values of $q$ such that a countably infinite collection of disks, whose areas form an infinitely decreasing geometric progression with the start value ...
13
votes
1answer
171 views

Expected values of some properties of the convex hull of a random set of points

$N$ points are selected in a uniformly distributed random way in a disk of the unit radius. Let $P(N)$ and $A(N)$ denote the expected perimeter and the expected area of their convex hull. For what ...
12
votes
2answers
300 views

n-simplex in an intersection of n balls

Consider a $n$-simplex, $n \geq 2$ with vertices $x_i,i=1,...,n+1$. For each edge $(i,j)$, consider $n$-ball $B_{ij}$ such that vertices $x_i$ and $x_j$ are antipodal on this ball. Fix a point $x_0$ ...
12
votes
2answers
339 views

Unit diameter pentagons with maximum area

In the euclidean plane, if one considers the set of quadrilaterals having unit diameter (maximum distance between two points in the convex envelope), it is quite easy to give a description of the ...
12
votes
1answer
478 views

Circles on the plane such that every line intersects at least one of them but no line intersects more that 100 of them

I have a serious problem with this problem: Is it possible to Draw circles on the plane such that every line intersects at least one of them but no line intersects more that 100 of them !? Any help ...
12
votes
0answers
139 views

Size of connected regions on a randomly-colored infinite chessboard

Consider an infinite chessboard where each square is colored white with probability $p$ and black with probability $1-p$. Suppose without loss of generality that the square at $(0,0)$ is white. We ...
11
votes
2answers
182 views

Is every shape possible with a snake?

Imagine a 2d snake formed by drawing a horizontal line of length $n$. At integer points along its body, this snake can rotate its body by $90$ degrees either clockwise or counter clockwise. If we ...
11
votes
2answers
458 views

Is the figure the circumference of a unit circle?

A friend of mine taught me the following question. I've never heard such a strange and interesting question! Qustion: Supposing that a figure $S$, which is constituted by points, satisfies the ...
11
votes
1answer
72 views

Coloring $\mathbb R^n$ with $n$ colors always gives us a color with all distances.

I wanted to share a really cool but simple problem. Consider a coloring of the points of $\mathbb R^n$ with $n$ colors. Prove that there is a color $c$ such that for any $r>0$ there are two points ...
10
votes
4answers
176 views

A circle with $500$ points in its interior

Given any $1000$ points in the plane, show that there is a circle which contains exactly $500$ of the points in its interior, and none on its circumference. How do I approach this problem? I feel ...
10
votes
1answer
172 views

Minimum number of hemispheres covering a sphere

Here is a question which seems easy but seems to have many pitfalls. If I give you an arbitrary covering of the sphere by $N$ closed hemispheres. You can pick any of the hemispheres to keep. What is ...
10
votes
1answer
212 views

Biggest Little Polyhedron

The Biggest Little Polygon problem asks for the polygon with greatest area where the largest diameter is 1. Let's add a dimension and find the largest volumes. What is the biggest little polyhedron ...
10
votes
2answers
190 views

What is the expected convex depth of a set of $m$ randomly chosen points in the unit square?

Definition. Let $X$ be a set of points in $\mathbb{R}^2$. Then the vertex sequence of $X$ is defined by $X_{0}=X$, and $X_{i+1}=\left\{x\in \operatorname{Conv}(X_{i}): x \notin ...
10
votes
2answers
169 views

Partitioning the plane into three sets each intersecting the vertices of every square with side 1?

Q1. Is it possible to partition the plane into three sets such that each of them contains at least one vertex of every square with side 1 ? (I mean all squares of side-length 1, not just those with ...
10
votes
1answer
173 views

How many hyperplanes does it take to separate $n$ points in $\mathbb{R}^m$?

By 'separate', I mean that each point lies in its own little region/cell. For instance, it takes a minimum of $P = 4$ lines to separate $n = 7$ points in $\mathbb{R}^2$ ($m=2$), assuming that no 3 ...
10
votes
1answer
182 views

Number of ways to dissect a square into triangles of equal area

Monsky's theorem states that it is impossible to dissect a square into an odd number of triangles of equal area. If $n$ is an even integer, I am interested in the number of ways of dissecting a ...
10
votes
1answer
193 views

$2013\times2013$ Board with no trominoes.

Let A be a $2013\times2013$ board with $k$ black squares and containing no $L$ shaped black trominoes(in any rotation) and such that if any white square is dyed black then $A$ contains a black $L$ ...
8
votes
2answers
232 views

Do two closed subsets of $[0, 1]$ with measure $\frac{1}{2}$ intersect?

Let $A$ and $B$ be two closed subsets of $[0,1]$, each with a length of $1/2$. Is it always true that $A\cap B\neq \emptyset$? My intuition is yes, because: Either they intersect in their interior; ...
8
votes
3answers
206 views

Minimal circle containing set of points

Suppose that there are $n$ points in the plane $x_1, x_2, \dots x_n$, and $C$ is the minimal circle (the circle with the minimal radius) that contains all of them. If there is another point $p$ ...
8
votes
2answers
3k views

IMO 2013 Problem 6

Let $n\geq 3$ be an integer, and consider a circle with $n+1$ equally spaced points marked on it. Consider all labelings of these points with the numbers $0,1,\dots, n$ such that each label is used ...
8
votes
1answer
182 views

Points “seeing” each other in a loop

For two points $P,Q$ with integer coordinates in $2$ dimensions, we say that $P$ "sees" $Q$ iff the segment $PQ$ contains no other points with integer coordinates. Do there exist points ...
8
votes
1answer
98 views

Minimum number of circles with 3 neighbors

It is possible to arrange congruent circles on the plane in such a way that no two circles overlap and each circle adjoins exactly three other circles. The picture shows an example with 16 circles. ...
8
votes
1answer
167 views

Is this curve the circumference of a circle?

Let $\Gamma$ be a single closed curve with no self-intersections on a plane which satisfies the following condition : Condition : For any distinct four points $P, Q, R, S$ on $\Gamma$, if the line ...
8
votes
1answer
97 views

How to prove that $5$ unit hypercubes cannot be positioned to cover a unit hypersphere?

How to prove that $5$ unit hypercubes cannot be positioned to cover a unit hypersphere? The unit hypersphere has hypervolume $\frac{\pi^2}{2} \approx 4.93 \lt 5$ but it seems unlikely that it is ...
8
votes
1answer
166 views

Counting subsets of lattice points

Let $n\ge 2$, and consider the set of $\binom{n}{2}$ lattice points in the interior of the triangle with vertices $(0,0)$, $(0,n+1)$ and $(n+1,n+1)$. For $r\le \binom{n}{2}$, let $f(n,r)$ be the ...
8
votes
0answers
55 views

Ratio of product from one point and minimum distance

Given points $A_0,A_1,\ldots,A_n$ in the plane, let $m$ denote the minimum distance among any two points. What is the minimum value of $$\dfrac{|A_0A_1|\cdot|A_0A_2|\cdot\ldots\cdot|A_0A_n|}{m^n}?$$ ...
8
votes
0answers
196 views

What is the shape of the convex $n$-gon which gives the maximum of a function?

Supposing that the length of every edge of the convex $n$-gon $P_1P_2$$\cdots$$P_n$ is 1, what is the shape of the $n$-gon which gives the maximum of the following function $A_n$? ...
7
votes
1answer
81 views

How many unit squares can overlap a given unit square without overlapping each other?

How many unit squares can overlap a given unit square without overlapping each other? @calculus has managed to arrange 7 squares (see this GeogebraTube page). This seems like the maximum ...
7
votes
1answer
188 views

Finding total number of self avoiding paths for $n\times n$ grid

we call a connected part of $n\times n$ grid "N-mino" if it has these 2 conditions it should contain $(n,n)$ if it contains $(i,j)$ then it should contains at least one of $(i+1,j)$ or $(i,j+1)$. ...
7
votes
2answers
358 views

Is there a simple proof of Borsuk-Ulam, given Brouwer?

(Brouwer) Any continuous function from a convex compact subset K of a Euclidian space to itself has a fixed point. Given this lemma, is there a simple proof of: (Borsuk-Ulam) Any continuous ...
6
votes
1answer
162 views

Partition rectangle into finite number of squares

For what positive real numbers $x,y$ can an $x\times y$ rectangle be partitioned into a finite number of squares? When $\dfrac{x}{y}$ is a rational number, it is not hard to see that we can partition ...
6
votes
2answers
193 views

Squaring the plane, with consecutive integer squares. And a related arrangement

Q1. I was fiddling around with squaring-the-square type algebraic maths, and came up with a family of arrangements of $n^2$ squares, with sides $1, 2, 3\ldots n^2$ ($n$ odd). Which seems like it would ...
6
votes
3answers
199 views

Is there a non-constant function $f:\mathbb{R}^2 \to \mathbb{Z}/2\mathbb{Z}$ that sums to 0 on corners of squares?

A problem in the 2009 Putnam asks about functions $f:\mathbb{R}^2 \to \mathbb{R}$ such that whenever $A,B,C,D$ are corners of some square we have $f(A)+f(B)+f(C)+f(D)=0$. Without spoiling the problem ...
6
votes
1answer
206 views

How many unique shapes can be created from a wiggly snake of $k$ links?

In one of her videos (at 0:46) Vihart muses about this problem. Given a wiggly plastic snake with $k$ links, how many valid and unique shapes can be created out of the snake. A shape is valid if it ...
6
votes
1answer
69 views

The largest regular m-gon that fits inside a regular n-gon

This question just popped into my head while doing some "for fun" math. More precisely: Let $m,n\in\Bbb{Z};m,n>2$. Let $P$ be a regular $n$-gon (let's say $P$ is the convex hull of the $n$ $n$th ...
6
votes
1answer
205 views

In a planar 6-point set of diameter at most 2, how many distances can be greater than $\sqrt{2}$?

I found a tough combinatorial geometry problem. Any discussion or advice is helpful. 6 points are on the plane such that any 2 points are at most distance 2 apart. What is the most number of pairs of ...