Questions tagged [combinatorial-geometry]

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.

3
votes
2answers
205 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 ...
4
votes
2answers
117 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 $...
22
votes
1answer
1k 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?
5
votes
0answers
118 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 ...
1
vote
2answers
2k 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 ...
4
votes
2answers
74 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 ...
1
vote
2answers
46 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 ...
8
votes
1answer
225 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)$. ...
5
votes
1answer
162 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
0answers
157 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 $\...
1
vote
0answers
42 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?
9
votes
2answers
1k 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 ...
0
votes
1answer
347 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 $\...
2
votes
1answer
1k 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
0answers
122 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
278 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 ...
7
votes
0answers
182 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-...
2
votes
0answers
82 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.
6
votes
0answers
369 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 ...
6
votes
1answer
265 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 ...
1
vote
1answer
154 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$. ...
4
votes
2answers
264 views

Olympiad : The maximum number of pairs whose distance is $1$ when any pairwise distance is at least $1$

Consider the ten points in the plane. Each distance between any two points is larger than or equal to $1$. Then what is the maximum number of pairs whose distance is $1$? I guess that the answer is $...
2
votes
3answers
199 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 $\left|z_{1}\right|+\left|z_{2}\right|+\left|z_{3}\right|+\left|z_{4}\...
3
votes
1answer
126 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 ...
1
vote
0answers
190 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 d}\left(x_{i}+x_{j}-\sqrt{...
8
votes
3answers
266 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 ...
2
votes
0answers
219 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 ...
3
votes
2answers
153 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. ...
0
votes
2answers
211 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 person ...
4
votes
1answer
528 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 ...
5
votes
2answers
118 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 ...
2
votes
2answers
1k 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 ...
17
votes
2answers
367 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 $t=0$...
2
votes
1answer
2k 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 ...
0
votes
0answers
92 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 Sperner’s ...
0
votes
0answers
101 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 diagram on ...
2
votes
0answers
212 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 ...
74
votes
1answer
5k 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 ...
14
votes
4answers
1k 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 ...
0
votes
1answer
363 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. ...
8
votes
0answers
361 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 ...
4
votes
0answers
56 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$, ...
1
vote
0answers
464 views

Generalizing Euler's Polyhedral Formula for Graph Embeddings in Higher Dimensions.

In the plane, Euler's Polyhedral formula tells us that $V - E + F = \chi$, where for graph embeddings we have that $\chi = 1$. Alternatively, we can think of a graph embedding as a simplicial $1$-...
5
votes
0answers
202 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 ...
1
vote
1answer
239 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 $f_{...
2
votes
1answer
269 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 (...
2
votes
1answer
187 views

Mathematical Results from Counting Points in Lattices

I'm preparing a talk on lattice point enumeration in polytopes (Ehrhart-Macdonald Theory), and I'd like to have an introduction with a few motivational problems/results which arise from the ...
7
votes
2answers
671 views

Counting Lattice Points with Ehrhart Polynomials

Let $\bar{\mathcal{P}}$ denote the closed, convex polytope with vertices at the origin and the positive rational points $(b_{1}, \dots, 0), \dots, (0, \dots, b_{n})$. Define the Ehrhart quasi-...