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.

188 questions
818 views

Geometric way to view the truncated braid groups?

This is perhaps a vague question, but hopefully there exists literature on the subject. The question is motivated by an answer I gave to this question. I also asked a related question on MO, although ...
275 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$ ...
306 views

Hard problem in combinatorial geometry

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 ...
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 ...
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-...
62 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" ...
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 ...
50 views

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 ...
274 views

Geometric interpretation of k-th power of first n natural numbers and summation using Pick's theorem

I want to know is there any interesting properties of this approach or generalization to find $S_k(n)=1^k+2^k+3^k+\cdots+n^k$ by using Pick's Theorem $S=i+\tfrac{b}{2}-1$, where $i$-number of ...
141 views

Minimum number of points chosen from an $N$ by $N$ grid to guarantee a rectangle?

What is the maximum number of points that can be chosen from an $N$ by $N$ grid such that no $4$ of the chosen points form a rectangle with sides parallel to the axes of the grid? Equivalently, what ...
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 ...
157 views

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$, ...
60 views

Maximum number of umbrellas that can be added in a one kilometer beach?

Suppose we have a beach of length $1-$km. Suppose one Day $0$, the beach is empty. One day $1$, a family comes and puts their umbrella at some point in the beach. This point is fixed forever and ...
34 views

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 ...
66 views

Relationship between Affine Dependence and Linear Dependence in Oriented Matroids?

I'm reading "Lectures on Polytopes" by Gunter Ziegler. The author first introduces the components of oriented matroids in affine case, then making a transition to linear case, with the condition "1z ...
143 views

81 views

A problem in elementary combinatorial space geometry.

Also asked on overflow: https://mathoverflow.net/questions/296567/some-elementary-schubert-calculus-calculations/296583#296583 Consider $3$ dimensional projective space (although you don't have to ...
66 views

Cutting disk into more than 8 parts of equal area by 4 lines

Is it possible to cut unit disk in more than 8 parts of equal area (possibly not congruent) by 4 lines? It's can be proved that it's impossible to cut circle in 7 parts by 3 lines. For example, here ...
How many ways can hexagonal tiles can be arranged in a triangle? Let us assume that there is an equilateral triangle of side $s$. The triangle is subdivided by edges on $b$ segments, so that there ...