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

3
votes
1answer
49 views

Geometry textbook

I am planning to take a graduate Geometry course next semester. The preliminary syllabus does not specify any textbook but has the following descriptions: Catalog Course Description: This course ...
3
votes
1answer
59 views

Placing n points in a MxM square grid

I am facing an apparently well-known problem: placing $n$ points in a discrete grid so that the points are 'evenly' distributed. By evenly I mean that I would like the density of points to be nearly ...
1
vote
0answers
26 views

Bridge Number , Knot Theory

I had been reading some knot theory lately and got to know about a whole classification of 2-bridge knots , does their exist any such extensive study over 3-bridge knots?
4
votes
0answers
77 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 ...
1
vote
4answers
251 views

What is the maximum number of pieces that a pizza can be cut into by 7 knife cuts? (NBHM 2005)

I am seeing this question very first time and do not know any formal way to solve it. Which part of mathematics it is related to? What is the maximum number of pieces that a pizza can be cut into by ...
1
vote
1answer
50 views

How many regions are created by the set of all hyperplanes defined by a set of points?

If we have a set of points X in d-dimensional euclidean space, and we look at the set of all n-dimensional hyperplanes that are defined by any subset Y of X (in the sense of being the unique ...
2
votes
3answers
72 views

Separating $3n$ points on the plane by a line

I am trying to solve a problem in geometry (a contest-type question), and I wondering if the following result is true. (If it is true, then it makes life much easier!) Suppose there are $3n$ ...
2
votes
0answers
59 views

The Erdős-Szekeres problem on points in convex position

The Erdős-Szekeres problem on points in convex position and its proof using Ramsey theorem are well know. The problem goes like this: For every natural number $k$ there exists a number $n(k)$ such ...
4
votes
0answers
41 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 ...
1
vote
2answers
34 views

How many marbles must be placed in a square area of $16 in^2$ to ensure that two of the marbles are within $2 \sqrt{2}$ inches of each other?

How many marbles must be placed in a square area of $16 in^2$ to ensure that two of the marbles are within $2 \sqrt{2}$ inches of each other? Wouldn't even know how to begin this question.
0
votes
1answer
47 views

A combinatorial action of a discrete group is proper if and only if it has finite vertex stabilizers

First, let me fix some definitions. The action of a group $G$ on a topological space $X$ is proper if for every compact subspace $K \subseteq X$ the set $\{g \in G \ | \ g K \cap K \neq\varnothing ...
10
votes
2answers
248 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 ...
10
votes
1answer
67 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 ...
1
vote
0answers
40 views

Generalization of Minkowski's theorem

I would like to prove a generalized version of the Minkowski's theorem, but I don't quite know how to do it. Here is what I would like to prove: Let $X\subset \mathbb{R}^d$ is convex, symmetric ...
8
votes
0answers
83 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 ...
24
votes
3answers
478 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 ...
2
votes
1answer
41 views

Marking the point closest to each point

We have $6000$ points in the plane. All distances between every pair of them are distinct. For each point, we mark red the point nearest to it. What is the smallest number of points that can be marked ...
4
votes
0answers
72 views

Dirichlet's approximation theorem (simultaneous version): proof via Minkowski's theorem

There is a proof of the Dirichlet's approximation theorem based on Minkowski's theorem. The proof is given on wikipedia (http://en.wikipedia.org/wiki/Dirichlet%27s_approximation_theorem) and it is ...
31
votes
2answers
1k 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 ...
3
votes
1answer
99 views

pigeonhole principle on a circle

In a disk of radius 10, how can we find all values n such that there are exactly n points in the disk and such that no matter how the n points are arranged, we can draw a disk with radius 1 in the ...
9
votes
1answer
97 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 ...
4
votes
2answers
104 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, ...
1
vote
2answers
66 views

Dicrete Math Interesting question about Tromino

Prove that for a m$\times$n rectangle, if this rectangle can be covered completely by trominoes of the shape indicated in the picture, then mn is divisible by 3. I came up with a tentative way to ...
5
votes
6answers
274 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$). ...
6
votes
1answer
224 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 ...
8
votes
1answer
142 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 ...
4
votes
2answers
140 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, ...
0
votes
1answer
200 views

Set of points in the plane which is intersected by every line on the plane and in which no more than K points are collinear

Question Let $K \in \mathbb{N} (K \geq 3)$ and $r \in \mathbb{R}^+$. Either find a set $S$ of points in the plane such that every line on the plane intersects atleast one point in $S$ and ...
1
vote
2answers
53 views

Choosing sets of vectors on a complex sphere

Consider a complex $t$ dimensional unit sphere. Can we have $t$ sets of $2^t$ vectors $v_{ij}\in \Bbb C^t$ on the sphere where $i=1$ to $t$ and $j=1$ to $2^t$ on this with inner products satisfying ...
1
vote
1answer
23 views

Choosing vectors on a complex sphere

Consider a complex $t$ dimensional unit sphere. Say we pick $n$ points on this with inner products in the set $\{a_1,a_2,\dots,a_r\}$ (we have $n$ inner products with value $1$). Note the set ...
0
votes
1answer
666 views

How many circles of radius r fit in a single bigger circle of radius R?

Is there any formula to calculate how many circles of radius r fit in a single bigger circle of radius R? I'd apreciate if it didn't involve advanced math, like calculus (unless there is no other way, ...
0
votes
1answer
84 views

Question related to Desargues' Theorem

The diagram below is one way of drawing two triangles ($\Delta PQR,\ \Delta P'Q'R'$) perspective from a point ($O$), with pairs of corresponding sides meeting at $D, E, F$ as in Desargues' Theorem ...
3
votes
0answers
87 views

Fitting cubes inside a bigger cube

Suppose the sum of the volumes of $n$ cubes is 1. Then no matter what $n$ is I need to prove they can be put inside a cube of volume $\leq 2$ such that they do not overlap. I am totally going nuts ...
3
votes
3answers
159 views

Proving a point inside a triangle is no further away than the longest side divided by $\sqrt{3}$

Problem: In a triangle $T$ , all the angles are less than 90 degrees, and the longest side has length $s$. Show that for every point $p$ in $T$ we can pick a corner $h$ in $T$ such that the ...
8
votes
1answer
85 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 ...
11
votes
2answers
430 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
421 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 ...
3
votes
0answers
132 views

Squaring rectangles

it is a nice high-school exercise to prove that a square can be tiled with n squares if and only if n=1, 4 or is any integer greater or equal to 6. A direct consequence is that any rectangle that can ...
6
votes
0answers
77 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$ ...
3
votes
1answer
146 views

Dividing a set of points into two sets of roughly equal diameter

Let $S$ be a finite set whose cardinality is more than 1 and $d: S\times S\rightarrow\mathbb R$ be a positive symmetric function (that is, $d$ is a distance without the axiom of triangle inequality). ...
4
votes
2answers
121 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
1answer
62 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 ...
9
votes
1answer
169 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$ ...
16
votes
1answer
458 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: ...
5
votes
2answers
112 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)
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 ...
1
vote
0answers
36 views

Fixed Length Cycle Search

I am given a list of $0 \le M \le 2n(n-1) $ edges of a graph. My goal is to find a connected subgraph of this graph such that the degree of every vertex in the subgraph is $n$ that has exactly $n$ ...
0
votes
2answers
113 views

Proof of the following: How many $(n-2)$ dimensional faces from a corner of a hypercube

I asked a question earlier regarding the number of $(n-2)$ dimensional faces exiting a corner of an $n$ dimensional hypercube. (For example the number of points in a corner of a square, or the number ...
4
votes
1answer
85 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 ...
5
votes
0answers
134 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$? ...