Mathematics Stack Exchange
Mathematics Stack Exchange

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.

Combinatorial geometry (a term coined by H. Hadwiger in 1955) comprises the study of geometric objects arranged and combined with regard to discrete properties, esp. incidence relations. It is in this sense a strict subset of discrete and computational geometry topics.

Some representative results in this area are Helly's theorem and Pick's theorem. Recent formal verification of Hales' proposed proof of Kepler's conjecture demonstrates the breadth of tools from analysis as well as discrete mathematics that are useful. Many open problems have been proposed in this area.

890 questions
63
votes
5 answers

In how many different ways can a 9-panel comic grid be used?

While writing my answer to Why does “Watchmen” use the 9-panel grid? I used this picture to indicate the many ways it can be divided into groups (which may be used for the panels of a comic, as was the case in “Watchmen”): Image source…
Gallifreyan
  • 767
  • 1
  • 6
  • 11
8
votes
1 answer

We have $n$ points in a plane. Show that there is at least $\lfloor {\sqrt{n\over 2}} \rfloor $ different distances between them.

We have $n$ points in a plane. Show that there are at least $\lfloor \sqrt{n\over 2} \rfloor $ different distances between them.
nonuser
  • 90,026
8
votes
1 answer

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 is known that when $k$ is odd $S_k(n,n)=0$ (For…
Ajat Adriansyah
  • 985
7
votes
2 answers

An example of a similar universal cover for 5 points.

Let's say that $A\subset\mathbb{R}^2$ is a similar universal cover for $n$ points if: $A$ is closed. The interior of $A$ is empty. For every finite set $B\subset\mathbb{R}^2$ containing exactly $n$ points there is a set $A'\subset\mathbb{R}^2$…
Sergio Enrique Yarza Acuña
  • 1,057
7
votes
2 answers

Circle through four lattice points

Let $n\geq 2$. What is the minimum $k$ so that if we take $k$ lattice points on the plane with each coordinate between $1$ and $n$ inclusive, then some four points lie on a circle? If we find a $k$ so that some four points must be vertices of a…
user336268
  • 2,339
6
votes
1 answer

Polygonal line in a square

A polygonal line of the length $1001$ is given in a unit square. Prove that there exists a line parallel to one of the sides of the square that meets the polygonal line in at least $500$ points. My try : I haven't done much. I tried to take a very…
shadow10
  • 5,616
5
votes
0 answers

Color the edges and diagonals of a regular polygon

Here is the problem: For what $n$ is it possible to color the edges and diagonals of an $n$-side regular polygon with $\dfrac{\binom{n}{2}}{3}$ colors, such that you use every color exactly three times and for every color the three segments (edges…
user173628192
  • 1,506
4
votes
0 answers

Erdos Distance Problem

In the Guth/Katz solution to the Erdos Distance problem on $N$, we have that the minimum distances is given by considering an approximate grid. Let's have $N=n^2$, so the grid is exactly the $n \times n$ grid. I am a little confused why this is the…
user154035
  • 153
4
votes
1 answer

Szemerédi-Trotter theorem unit area triangles

Let $P$ be a set of $n$ points in the plane. Show that there are at most $O(n^{7/3})$ triangles of unit area whose vertices are from $P$ by using Szemeredi-Trotter theorem.
trung chum
  • 51
  • 1
4
votes
2 answers

Strange succession

An ant starts from the origin of a cartesian plane and makes $n \ge 2$ steps of lengh $d_1, d_2, \cdots, d_n$. Is there a condition (necessary and sufficient) on $d_i$'s for which the ant can come back to the origin after the $n$ steps? (The ant…
Lance
  • 401
3
votes
1 answer

Getting out of a convex forest

This problem is giving me the hardest time: Alex is lost in a forest. The forest area has a convex shape whose area is $P$. Prove that Alex can choose a path not longer than $\sqrt{2 \pi P}$ such that he will exit the forest for sure. This is from…
VividD
  • 15,966
3
votes
0 answers

Prove that regular polygon whose vertices lie on lattice points in $\mathbb{R}^2$ is a square

Prove that a regular polygon whose vertices lie on lattice points in $\mathbb{R}^2$ is a square. Here is my progress: Say $n > 9$ is the smallest positive integer such that a regular $n$-gon has its vertices lying on lattice points (the other base…
stryx
  • 47
3
votes
0 answers

Subsets of the circle not contained in a semi-circle

I'm reading a paper (Bullett and Sentenac, "Ordered orbits of the shift...", Ergodic Theory and Dynamical Systems), and have found that a proposition (Proposition 1) is (1) slightly incorrect (I have found a counterexample to the proposition that is…
anthonyquas
  • 1,017
  • 5
  • 15
3
votes
1 answer

Combinatorial Geometry IMO 2017 Problem 3

A hunter and an invisible rabbit play a game in the Euclidean plane. The rabbit's starting point, $A_0,$ and the hunter's starting point, $B_0$ are the same.After $n-1$ rounds of the game, the rabbit is at point $A_{n-1}$ and the…
user410845
3
votes
1 answer

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 know where to start. Thanks
tangkhaihanh
  • 917
1
2 3 4