# 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.

209 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
254 views

### Ratio of product from one point and minimum distance

Given points $A_0,A_1,\ldots,A_n$ in the plane, let $m$ denote the minimum distance among any two points. What is the minimum value of $$\dfrac{|A_0A_1|\cdot|A_0A_2|\cdot\ldots\cdot|A_0A_n|}{m^n}?$$ ...
253 views

### $200n$ diagonals are drawn in a convex $n$-gon. Prove that one of them intersects at least $10000$ others.

$200n$ diagonals are drawn in a convex $n$-gon. Prove that one of them intersects at least $10000$ others. There was no information about $n$ in a original problem. Attempt: Choose at random and ...
340 views

### Maximum number of regions of a sphere partitioned by $\binom{n}{3}$ planes from $n$ points

We can place $n\in\mathbb{N}$ points on the surface of a sphere in a configuration so as to maximize the answer. A plane is defined by $3$ points. We create all $\binom{n}{3}$ planes from the $n$ ...
1k views

### Fractal Pattern from Queen's Move Construction

This question relates to the OEIS sequence A279212. Fill an array by antidiagonals upwards; in the top left cell enter $a(0)=1$; thereafter, in the $n$-th cell, enter the sum of the entries of ...
360 views

### Prove 2017 points in a plane cannot form 2017 triangles with the largest area

I haven’t got an idea about this problem . Could someone help me? Suppose 2017 points in a plane are given such that no three points are colinear. Among the triangles formed by any three of these ...
199 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-...
413 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 ...
72 views

### Is this kind of “Gerrymandering” NP-complete?

Consider the following simplified form of "Gerrymandering": You have $n^2$ squares arranged as an $n\times n$ matrix. Each square is marked with either $0$ or $1$ which means a "voter preference" ...
287 views

87 views

### Counting the partitions of a square into triangles

$\textbf{Problem:}$ The player has cut a square into $57$ triangles and painted a blue dot at all their vertices. It turned out that the blue dots are only inside the square (not on the sides) and in ...
53 views

### Linear bound on maximal rectangle in a permutation

Given $n$ coloured squares in an $n$ by $n$ square board of unit squares, one in each row and column (which we will call a permutation), let the minimum area (over all permutations) of the largest ...
33 views

### If every three segments from set have common interesecting line, than there exist line passing through all segments from this set

There are given lines segments in a plane such that for any three of them there exists a line intersecting them. Prove that there exists a line intersecting all these segments. Perhaps I should use ...
95 views

### Number of possible 'chains' made from $n$ rings

If we have $n$ rigid circles of the same radius we can form 'chains' on the plane by placing them in such a way that they intersect (here two circles intersect if and only if they have $2$ common ...
160 views

### How to prove the solution of these inequalities is empty?

Prove: There does not exist 4 unit vectors $\mathbf{v}_1$, $\mathbf{v}_2$, $\mathbf{v}_3$, $\mathbf{v}_4$ in $\mathbb{R}^3$ such that  \left \{ \ \begin{array}{ll} \dfrac{4}{3} < \left \|\...
592 views

### $\epsilon$- net theorems

Here we are going to consider problems of the following type: We have a family set F of satisfying certain conditions, meaning that we can choose a bounded number of points such that each set of F ...
172 views

### Hypercube subdivision for a combinatorial problem

I have to design a combinatorial algorithm based on some simmetries of an hypercube and I'm pretty sure such a problem has already been studied. Let's start with a 3D case. Consider a cube like the ...
I want to tile the plane with equal-sized regular polygons of $n$ sides. Obviously for some $n$, the tiles will be able to tessellate and cover the whole plane (e.g triangles, squares, hexagons) I ...