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

902 questions
Filter by
Sorted by
Tagged with
69 views

### A version of Helly's theorem without convexity but connectivity

It's more than 100 years since Helly's celebrated theorem in discrete geometry was published by him, and yet ghosts still remain. The theorem in it's infinitary glory states Let $\{X_j\}_{j\in J}$ be ...
• 1,882
121 views

### About countable family of sets in R satisfying a hitting condition

I was working on a problem when I hit a little snag about a geometric problem. To properly describe it, let me introduce some notions. We say that a point $p$ hits a set $X$ if $p\in X$. We say that ...
53 views

### Conway's Angel Problem: Strategy for Devil to catch 1-Angel

I am learning about Conway's Angel Problem, which is in the image below. How can the Devil devise a strategy that will successfully capture the $1$-Angel, or an angel of power $1$, which is also a ...
• 111
45 views

### Counting transitions between sticks and stones configurations for extended objects

Suppose that we have a circle around which $L$ buckets are arranged. We have $k$ balls to distribute among the buckets and each bucket can contain at most one ball. Given a configuration of the balls, ...
• 285
1 vote
26 views

### Maximize number of regions whose sides reach all vertices of $K_n$

Suppose we put $n$ points (vertices) in the plane and connect all pairs with edges, i.e. draw the complete graph $K_n$ in $\mathbb{R}^2$. (For simplicity, we can assume no $3$ vertices are collinear ...
97 views

### Sticks and stones for extended objects

Suppose that we have a circle around which $L$ buckets are arranged. We have $k$ balls to distribute among the buckets and each bucket can contain at most one ball. For the purpose of this discussion ...
• 285
13 views

### Estimates on Covering Number for Convex Polytopes Partitioning a Convex Set

Consider a convex set $K\in\mathbb{R}^3$ and a collection of convex 3-polytopes $C^i\subseteq K$ of equal volume $\frac{1}{N}$ for $i\in(1,\ldots,N)$ that partition $K$ (a Voronoi or Laguerre diagram ...
1 vote
52 views

### Maximal irregular polygon inside a regular polygon

Problem: We have a regular $n$-gon. We want to choose some of it's vertices ($A_1, A_2, \ldots, A_m$), so these vertices form a completely irregular $m$-gon. Meaning that all of it's sides have ...
53 views

### Has this random process been studied on grid graphs?

As an offshoot of a different discussion I got curious about (uniform) random spanning trees on grid graphs (torus graphs in particular, to avoid having to think about edge effects) and what their ...
• 51.9k
18 views

### Convex distance on the Boolean cube

The convex distance (or Talagrand distance) can be defined as $\sup_{\alpha}\inf_y d_\alpha(A,x)$, where $d_\alpha$ is the weighted Hamming distance, that is $d_\alpha(x,y)=\sum_{x_i\neq y_i}\alpha_i$,...
• 992
81 views

### Monochromatic Triangles with Lattice Centroids in $\mathbb{Z}^2$

There is this problem proving that every $2$-colouring of the lattice points of $\mathbb R^m$ has a collection of $n$ monochromatic points whose centroid is a lattice point of the same colour and I ...
1 vote
18 views

### What class of subgraphs of the $n$-hypercube graph characterizes the region graphs of arrangements of $n$ hyperplanes in $\mathbb{R}^d$?

I am looking for a reference that answers or at least discusses the question in the title. I browsed Sergei Ovchinnikov's book "Graphs and Cubes" and several lecture notes on hyperplane ...
• 231
25 views

### Do all >1D box fractals really have lines in them?

Consider an $n \times n$ square split up into $n^2$ cells the natural way. Now suppose we fill in $1 \le k \le n^2$ of these cells s.t. $\log_n(k) > 1$. Is it always the case that there will be a ...
• 17.3k
17 views

### How can I show in a formal way this solution of Bezdek-Connelly Theorem?

Question Show that for $n=4$, the Bezdek-Connelly theorem is tight: there exists 4 unit circles in the plane such that every two circles intersect at exactly two points, and there are exactly 4 ...
• 437
35 views

### Is there any Example of 8 Points in the Plane that Determine only 4 Ordinary Lines (Gallai Lines)?

I want to find an example of 8 points in the plane that determine only 4 ordinary lines (lines containing exactly 2 points). I have tried all the shapes I know, but I can’t seem to come up with an ...
• 437
32 views

### How Should I Prove there are at least Two Configurations for $9_3$?

Question Prove that there are at least two different geometric ($9_3$) configurations. To prove that two configurations are different, show that they are different as combinatorial configurations. ...
• 437
107 views

• 437
1 vote
65 views

• 773
70 views

### Minimum number of points to have a point inside every triangle formed by $n$ points

Place $n$ points in a general position on the plane. Call a set $S$ of any points stabbing if every triangle formed by the $n$ chosen points contains at least one point from $S$ in its interior. For ...
• 337
146 views

• 561