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.

548 questions
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 ...
117 views

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?
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 ...
347 views

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-...
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.
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 ...
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 ...
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$. ...
264 views

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 ...
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{...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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$...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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$, ...
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$-...
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 ...