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.

64
votes
0answers
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 ...
10
votes
0answers
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$ ...
8
votes
0answers
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 ...
8
votes
0answers
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 ...
7
votes
0answers
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-...
6
votes
0answers
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" ...
6
votes
0answers
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 ...
5
votes
0answers
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 ...
5
votes
0answers
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 ...
5
votes
0answers
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 ...
5
votes
0answers
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 ...
5
votes
0answers
157 views

Limits to the growth of the volume of a union of spheres

Assume that $x_i$, $i=1,\ldots,m$ are points in $\mathbb{R}^n$, with the maximal distance between any two of them being at most $1$. Define $$ a(r)=\mu\Bigl(\bigcup_{i=1}^m B(x_i,r)\Bigr),$$ where $\...
5
votes
0answers
202 views

Points and lines covering them

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 ...
4
votes
0answers
76 views

When are there $n$ elements in $\mathbb{Z}_n^2$ with all differences distinct?

For which natural number $n$ are there elements $\{x_i\}_{i=1}^n \subset \mathbb{Z}_n^2$ such that $x_i - x_j = x_k - x_l$ if and only if $i = k$ and $j=l$ (i.e. such that all differences between the ...
4
votes
0answers
141 views

Affine-regular hexagon in convex body

An affine-regular $n$-gon is a non-degenerate affine image of the regular $n$-gon. It seems to be a standard fact in combinatorial geometry that inside every convex compact set $K\subseteq \mathbb R^2$...
4
votes
0answers
45 views

Existence of fair parallel queues

I just spent a few days at a major theme park. The queue for one particular ride (involving pirates) bifurcated upon entry; the two sides wound independently through a maze and emerged next to each ...
4
votes
0answers
54 views

Area covered by one disk more than by two disks

Given are three unit disks on the plane. Let $A$ be the area of the plane covered by exactly $1$ disk. Let $B$ be the area of the plane covered by exactly $2$ disks. Prove that $A\geq B$. Intuitively,...
4
votes
0answers
159 views

Maximum number of acute triangles

Given $n$ points on the plane, no three of which are collinear, what is the maximum number of acute triangles formed by them? [Source: Based on Hungarian competition problem]
4
votes
0answers
156 views

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 ...
4
votes
0answers
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$, ...
3
votes
0answers
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 ...
3
votes
0answers
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 ...
3
votes
0answers
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 ...
3
votes
0answers
143 views

A Combinatorial Geometry Problem With A Solution Using Extremal Principle

I have solved this following Combinatorial Geometry Problem using extremal principle.Please check whether this solution is correct or not.Also write if you have any other solution. Problem :- Let $...
3
votes
0answers
99 views

hypercube subdivision

Let $n$ be a positive natural number. For all $\emptyset \subset S \subseteq \{1, \ldots, n\}$ and $k \in \mathbb{Z}$, define the hyperplane $H(S,k)$ in $\mathbb{R}^n$ given by the equations $$H(S,k):=...
3
votes
0answers
86 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 ...
3
votes
0answers
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 ...
3
votes
0answers
92 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 ...
3
votes
0answers
439 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 ...
3
votes
0answers
137 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 ...
3
votes
0answers
31 views

Hexagons share interior points

Can we draw infinitely many hexagons, not necessarily convex, on the plane so that any three of them share a common interior point, but no four of them does? For four hexagons this is possible, using ...
3
votes
0answers
215 views

What is the optimal tiling of a regular n-gon in the plane?

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 ...
3
votes
0answers
40 views

Maximum overlap of two convex bodies

Let $\Delta_n=\big\{(x_1,x_2,\ldots,x_n): \sum_i x_i \leq 1, x_i \geq 0\big\}$ denote an n-dimensional simplex. I am trying to find an $y \in \mathbb{R}^n$ such that the $y-$shifted negative simplex ...
3
votes
0answers
88 views

Center of mass of vertices without enumeration?

Given a $n$-dimensional convex polytope defined by $A x\leq b$ and $A_{eq} x = b_{eq}$, is there an efficient way to determine the average coordinates of all vertices without enumerating them? (As if ...
3
votes
0answers
195 views

Trajectories on a circular billiards table

This question is related to The case of Captain America's shield: a variation of Alhazen's Billard problem, but more focused. Let the unit disc in the plane be our billiards table, and let $C$ ...
3
votes
0answers
116 views

Filling a rectangle with squares of integer side length

How many ways are there to fill a $m\times n$ rectangles with squares that have integer side lengths? Both $m$ and $n$ are integers.
3
votes
0answers
91 views

Red and blue balls lined up

On a plane, is it possible to arrange $6$ red points and $6$ blue points such that No $2$ points coincide. For any line containing two or more points, not all the points on that line are of the same ...
3
votes
0answers
211 views

How many spherical caps of height $h$ and base circle radius $a$ can cover a sphere of radius $R$?

Question How many spherical caps of height $h$ and base circle radius $a$ can cover a sphere $\mathbb S $ of radius $R \quad (R \gg a)$? What I have thought so far Since the area of the sphere ...
3
votes
0answers
83 views

Given two lists of similar orthogonal matrices with common “conjugator”, determine that conjugator

Here's a question related to a long-time personal research project in combinatorial geometry. Suppose I have two lists of similar $n$-by-$n$ orthogonal matrices $P_i$ and $Q_i$, and suppose I know ...
3
votes
0answers
68 views

Realisations of associahedra

I seem to have lost the reference to a realisation I am interested in. Hopefully someone can steer me to a paper that fully explains the realisation. For the case $K_2$(the 5-gon) the following ...
3
votes
0answers
730 views

Fitting cubes inside a bigger cube

Suppose the sum of the volumes of $n$ cubes is 1. Then no matter what $n$ is I need to prove they can be put inside a cube of volume $\leq 2$ such that they do not overlap. I am totally going nuts ...
2
votes
0answers
39 views

Minimum diameter for $n$ points, given that distance between any two of them is greater than or equal to 1.

There are $n$ points on a plane, such that distance between any two of them $\geq 1$. Question is, what is minimum possible diameter for such set of points, that is minimum of distance between two ...
2
votes
0answers
75 views

Calculate the number of nonnegative integer solutions of $ax+by\leq c$.

If $a$, $b$, and $c$ are known, and $x$ and $y$ are integers greater than or equal to zero, how many possible values of ($x$, $y$) exist that satisfy the equation $$ax + by \le c\,?$$ I have ...
2
votes
0answers
123 views

Simple disproof of Danzer — Grünbaum conjecture

A set of points in $\mathbb R^n$ is acute if any three points from this set form an acute triangle. In 1962 Danzer and Grünbaum conjectured that cardinality of acute set in $\mathbb R^d$ is $2d-1$, no ...
2
votes
0answers
84 views

Probability of hypercube vertices being within the unit n-hypersphere

Three uniformly distributed i.i.d points inside the unit n-ball centered at the origin are picked $p_1, p_2, p_3$ they are chosen such that $\|p_1\|>\|p_2\|,\|p_3\|$ , where $\|p\|$ is the ...
2
votes
0answers
38 views

Covering the plane by circles centered on a discrete set

I have the following combinatorial/discrete analysis problem that arose while I was working on a problem in complex analysis, which in turn came from a problem in time-frequency analysis. Let $\...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
71 views

How many ways can hexagonal tiles of side a be arranged in a b*a sided triangle?

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 ...
2
votes
0answers
28 views

Contraction of oriented matroid as related to polytope?

I'm reading the following description of the contraction of oriented matroid, and its connection to polytopes: I have yet to find a numerical example to verify 6.13., but first I just want to check ...