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.
57
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 ...
17
votes
2answers
312 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 ...
13
votes
3answers
337 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 ...
12
votes
1answer
78 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?
8
votes
0answers
94 views
+50
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 ...
7
votes
1answer
125 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)$.
...
6
votes
3answers
146 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
134 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 ...
5
votes
1answer
86 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
2answers
82 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
1answer
83 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 ...
5
votes
0answers
147 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
42 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
0answers
57 views
Linear Independence Game
Suppose you have a set $X$ of vectors in $\mathbb{F}_2^n$, with $|X| \ge n+1$, and consider the following game. On their turn, each player (2 player game) chooses from $X$ one vector and sets it aside ...
4
votes
0answers
54 views
Points at Integer Distances in 3-space
With the restriction no three points in a line, no four points on a circle, there is a 7 point configuration of points on the plane such that all pairs of points are at integer distances. [1]
For ...
3
votes
2answers
50 views
Geometric solution to classic committee problem
Most people know the classic committe style problems.
I read this solution to one of the basic version of the committe problem and was impressed, but not sure why it works.
I was hoping someone ...
3
votes
1answer
47 views
Prove that the circles has at least a common point of intersection
In the interior of a unit square, there are $n(n\in \mathbb{N}^*)$ circles whose sum of areas is greater than $n-1$. Prove that the circles has at least a common point of intersection
I really don't ...
3
votes
2answers
74 views
Six points connected in pairs by coloured lines
Six points are connected in pairs by lines each of which is either red or blue. Every pair of points is joined. Determine whether there must be a closed path having four sides all of the same colour. ...
3
votes
0answers
90 views
dissection of rectangle into triangles of the same area
Given $m \times n$ rectangle with area $A$, and $m,n \in \mathbb{N}$. Let $S_k(m,n)$ be the number of way to dissect this rectangle into $k$ non-overlapping triangles whose area is $\frac{A}{k}$.
It ...
3
votes
0answers
39 views
Internal angle of a vertex of degree $d$ in $\mathbb{E}^2$ and $\mathbb{S}^2$
I am currently working on determining the maximum number of times the minimum spherical distance can occur among $n$ points in $\mathbb{S}^2$, and I have the following question.
In $\mathbb{E}^2$, ...
2
votes
3answers
69 views
Geometry - Equilateral triangle covered with five circles
I have to cover an equilateral triangle (whose sides are 1m long) with 5 identical circles: what's the minimum radius of the circles?
2
votes
3answers
189 views
Are there five complex numbers satisfying the following equalities?
Can anyone help on the following question?
Are there five complex numbers $z_{1}$, $z_{2}$ , $z_{3}$ , $z_{4}$
and $z_{5}$ with ...
2
votes
2answers
58 views
Lipschitz functions in $\mathbb{R}^n, \ \ \mathbb{R}^m$, extension
I've found the following lemma :
Let $\{x_1, . . . , x_k\}$ be a finite collection of points in $\mathbb{R}^n$
,
and let $\{y_1, . . . , y_k\}$ be a collection of points in $\mathbb{R}^m$, such that
...
2
votes
1answer
120 views
Minimum number of triangles a polygon of n sides belongs to
Let there be a regular n-sided polygon. A "minimalist" triangle is a triangle which has all vertices on vertices of n. let p be a point on this polygon. What is the minimal number of correct triangles ...
2
votes
1answer
110 views
Counting multidimensional structures (Chomp game states)
The game Chomp is described as follows on Wikipedia:
Chomp is a 2-player game of strategy played on a rectangular
"chocolate bar" made up of smaller square blocks (rectangular cells).
The ...
2
votes
1answer
265 views
How many shapes can one make with $n$ square shaped blocks?
How many possible shapes can one make by rearranging $n$ square shaped blocks, with and without allowing rotational symmetry? For example, for $n = 4$, there are seven possible shapes after ...
2
votes
0answers
23 views
Configuration analogues of projective spaces?
In a configuration, each point is incident to the same number of lines and each line is incident to the same number of points.
The Fano plane is a configuration, with 3 points on each line, and 3 ...
2
votes
0answers
58 views
Limits to the growth of the volume of a union of spheres
Assume that $x_i$, $i=1,\ldots,m$ are points in $\mathbb{R}^n$, with the maximal distance between any two of them being at most $1$. Define
$$ a(r)=\mu\Bigl(\bigcup_{i=1}^m B(x_i,r)\Bigr),$$
where ...
2
votes
0answers
72 views
Sorting combinations of linearly independent vectors
Given a set of $m$ vectors in $\mathbb{R}^n$ ($m > n$), sort all combinations of $n$ linearly independent vectors according to the determinant of the matrix whose columns are the $n$ vectors. ...
2
votes
1answer
37 views
Inner product between certain vectors on a simplex.
For $n\geq 2$, let $\Delta^n$ be a regular $n$-dimensional simplex in $\mathbb{R}^n$ centered at the origin ${\bf 0}$ and inscribed in the unit sphere $S^{n-1}$.
Let ${\bf v}_0,{\bf v}_1,\ldots,{\bf ...
2
votes
0answers
128 views
Minimum number of circles in a rectangle with no line in rectangle not intersecting any of them
Suppose we have a rectangle with sides $a$ and $b$, $a<b$, $a,b \in \mathbb R$. What is the minimum number of circles centered in the rectangle with radius $1$ such that each line passing through ...
1
vote
2answers
31 views
Why is an antipodal-symmetrically colored circle guaranteed to have an odd number of multicolored edges?
I'm reading a proof of 2D Tucker's Lemma. It asserts the following claim without proof:
Drop points on a circle in antipodal fashion (i.e. if there is a point at position $p$, then there also must ...
1
vote
1answer
55 views
Sum of angles in a polygon - Alternative solution
I was fascinated by this problem from the first moment I saw it.
Let $P$ be a convex polygon which has no two sides which are parallel. Each side $A_iA_{i+1}$ has a furthest away point $C_i$. ...
1
vote
1answer
99 views
Question about Euler's polyhedral formula in a proof of minimum distances
I am confused by a step made in a proof of the following result.
Let $f_{2}^{\text{min}}(n)$ denote the maximum number of times the minimum distance can occur among n points in the plane. Then ...
1
vote
0answers
31 views
Two coloured plane
Can you prove that For any two angles $θ,ϕ$ there exists a monochromatic triangle that has angles $θ,ϕ,180−(θ+ϕ)$ in two coloured plane?
1
vote
0answers
69 views
Does anyone know any specific example of such point set
Does anyone know any specific or explicit example of a set of $256$
points so that no $10$ are the vertices of a convex $10$-gon?
Thanks in advance.
1
vote
0answers
171 views
Does this hold?
Strayed on the following question. Assume that $x_{1}$,$\ldots$, $x_{d}\ge0$ with $x_{1}+\ldots+x_{d}=1$
and $y_{1},\ldots,y_{d}\in\mathbb{R}$. Does
$$
\min_{1\le i\ne j\le ...
1
vote
0answers
98 views
A question related to Helly's Theorem on convex sets
I have one question related to differential geometry. Initilally, I am giving some background and my question is after that.
Helly's Theorem
Let C be a finite family of convex sets in $R^n$ such ...
0
votes
2answers
92 views
Combinatorially equivalent polyhedra?
What does it mean for two polyhedra to be combinatorially equivalent? I've looked on the internet but in vain. If it's not a standard definition, then it might help to say that I found this term in a ...
0
votes
1answer
158 views
Packing Density of Tetrahedra - Explicit Calculations
I am researching problems relating to finding the optimal packing density of tetrahedra and I am driving myself crazy with the following very elementary calculations which do not seem to make sense.
...
0
votes
1answer
116 views
Maximum number of simplexes given n-element point sets in the plane
Does anyone know if it has been proved what the maximum number of simplexes occurring in the plane is for a given value of $n$ points? I am interested in this question in relation to packing problems ...
0
votes
0answers
63 views
The Snooker Table of Doom
A 'snooker' table (measuring 8 metres by 4m) with 4 'pockets' (measuring 0.5m and placed at diagonal slants in all 4 corners) contains 10 balls (each with a diameter of 0.25m) placed at the following ...
0
votes
0answers
35 views
Mega-sphere: The Revenge
A sphere 5.5 metres in diameter is filled with 1m diameter hemi-spheres.
(1) What is the theoretical maximum amount of hemi-spheres that
can be crammed into the big sphere ?
(2) By cramming them ...
0
votes
0answers
36 views
Proof of Sperner's Lemma
I am looking for a concise and mathematically robust proof of the Sperner's Lemma.
The easiest proof I found so far is Math Pages Blog, but I don't get it without few details.
Following is the proof ...
0
votes
1answer
56 views
Proof Strategy for intersecting lines.
Given $n$ (pairwise) nonparallel lines in $\mathbb{R}^2 $. $\lbrace L_1,\ldots,L_n\rbrace $. The intersection
of any two lines belongs to a third line in our set of lines. I would like to show that ...
0
votes
2answers
59 views
Permutating dance partners with least distance moved [duplicate]
Possible Duplicate:
Gay Speed Dating Problem
There are n (even) people at a dance and they dance in pairs. They do not care about gender (it is a very liberal disco). The goal is for each ...
0
votes
0answers
65 views
Brouwer’s fixed point theorem ⇒ Sperner’s lemma [duplicate]
Possible Duplicate:
Equivalence of Brouwers fixed point theorem and Sperner's lemma
Does anyone know a combinatorial proof of the implication from Brouwer’s fixed point theorem to ...
0
votes
0answers
56 views
can we represent the venn diagram on 4 sets $(A,B,C,D)$ with circular patterns. [duplicate]
Possible Duplicate:
Why can a venn diagram for 4+ sets not be constructed using circles?
can we represent the venn diagram on 4 sets $(A,B,C,D)$ with circular patterns.
Here's a venn ...
0
votes
0answers
52 views
Long-edge trisection of tetrahedra
I am studying refinements of triangular and tetrahedral meshes, in particular Longest-Edge (LE) partition methods. In any triangle there is obviously a longest edge and, on this edge there is a point ...
0
votes
0answers
75 views
Minimize the number of ellipses to cover a region
Suppose I have n ellipses, $\left\lbrace E_i \right\rbrace_{i=1}^n $; each ellipse, $E_i$, has the same area $A_1$. I want to completely cover a region (assume a rectangle) , $R$, with the least ...
