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

64
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 ...
34
votes
2answers
2k 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 ...
25
votes
3answers
511 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 ...
23
votes
4answers
498 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 ...
20
votes
1answer
326 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?
17
votes
2answers
333 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 ...
16
votes
1answer
580 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: ...
16
votes
0answers
164 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 ...
14
votes
4answers
442 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 ...
13
votes
2answers
529 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
107 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
1answer
296 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 ...
11
votes
2answers
439 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
2answers
283 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 ...
11
votes
1answer
431 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 ...
10
votes
2answers
188 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$ ...
10
votes
1answer
115 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
2answers
179 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
1answer
135 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
183 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$ ...
10
votes
0answers
111 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 ...
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
149 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
89 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
150 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 ...
7
votes
1answer
171 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
291 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 ...
7
votes
0answers
155 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
0answers
103 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 ...
6
votes
2answers
143 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
181 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
188 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
292 views

Minimum number of lines covering n points

Let there be n points in the plane. I want to know the minimum number of horizontal and vertical lines covering all the points in the plane. My initial approach started like this, 1) for each point I ...
6
votes
0answers
169 views

Expected Number of Convex Layers and the expected size of a layer for different distributions

It is well-known that the expected number of vertices on the convex hull of random set of points in the plane distributed uniformly within a $k$-gon is $O(k\log n)$ and within a smooth shape (e.g. a ...
5
votes
6answers
315 views

Covering a chess board with $2$ missing places with $31$ dominoes

I am reading a book that is intended to a wide audience (and not just mathematicians etc'), the book is, of course, about mathematics (Its still not clear about what exactly, I am only in page $2$). ...
5
votes
2answers
125 views

Orthogonal chords of compact sets

For any compact set on a plane say C does there always exist a chord in C such that its end points are orthogonal to the boundary of C (assumed smooth)
5
votes
1answer
120 views

Is There a Formalization of Cauchy's $F - E+V = 2$ proof?

Can anyone provide, or direct me to a formalized version of Cauchy's proof that for any convex polyhedron with $F$ faces, $E$ edges and $V$ vertices that $F - E + V = 2$. I am willing to accept the ...
5
votes
1answer
91 views

Which of the players will first draw a triangle?

6 vertices are given. No edges are given at first. Two players play the following game: the first player draws one black edge. Then the second player draws one green edge. Then the first player draws ...
5
votes
1answer
204 views

Characterisation of linearly separable points of a hypercube

Essentially, linearly separable points are just those corners that can be cut off with just one slice as marked out by a hyperplane. E.g. for a cube, the following 4 points (red) are not linearly ...
5
votes
2answers
98 views

primality on tiles?

Call $S_n$ the square of area $n^2$. See it as a collection of $n^2$ unit squares. In the following, what I call tile is a collection of unit squares that are glued together. If $n$ is not prime, say ...
5
votes
0answers
46 views

Erdos Distance Problem

In the Guth/Katz solution to the Erdos Distance problem on $N$, we have that the minimum distances is given by considering an approximate grid. Let's have $N=n^2$, so the grid is exactly the $n \times ...
5
votes
0answers
105 views

How many points you should draw in the square at least´╝č

There is a square, which side length is $2$, To ensure there exists a triangle in the square, with an area less than $0.5$, how many points should you draw in the square at least. the goal is for all ...
5
votes
0answers
166 views

Points and lines covering them

Let $n$ be a positive integer. A subset $S$ of points in plane satisfies the following conditions: a) We can't find $n$ lines in plane, such that every element of $S$ belongs to at least one of these ...
4
votes
2answers
168 views

An Olympiad Problem (tiling a rectangle with the L-tetromino)

An L block that is 3 unit blocks high and 2 unit blocks wide . It is true that if an n by m rectangle can be covered by such L blocks with out overlap that we would require an even amount of L blocks, ...
4
votes
2answers
145 views

Find the smallest triangulation of the n-dimensional

How to find the smallest triangulation of the n-dimensional cube into n- simplices? It is known, for example, that the 4D cube (the hypercube) may be partitioned into 16 4-simplices, and this is ...
4
votes
2answers
63 views

Planar graph with an exponential amount of matches?

I need a planar graph with an exponential amount of matches. Was wondering is there a good example of this? I'm finding it hard to believe that its possible to have such a graph. I was thinking ...
4
votes
2answers
108 views

Convex sets: a hint on how to solve a problem

Could anyone give me a hint on how to solve the following problem? Let $X_1, \dots, X_{d+1}$ be some finite sets in $\mathbb{R}^d$, such that the origin lies in ${\rm conv}(X_i)$ for all $i \in \{1, ...
4
votes
1answer
82 views

Euclidean Ramsey theory problem

Let $k\geq 1$ be given. Consider the following statement: For all (non equilateral) triangles (represented by 3 points in $\mathbb R^2$) and for all $k$-colorings of $\mathbb R^2$ there exists a ...
4
votes
1answer
90 views

Covering all the edges of a hypercube?

Consider an arbitrary $n$- dimensional hypercube: If we select $n - 1$ corners of that hypercube and highlight all $(n - 2)$ dimensional elements that originate from each of the corners is it ...
4
votes
0answers
43 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 ...