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.

learn more… | top users | synonyms

23
votes
0answers
298 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 ...
14
votes
0answers
165 views

Size of connected regions on a randomly-colored infinite chessboard

Consider an infinite chessboard where each square is colored white with probability $p$ and black with probability $1-p$. Suppose without loss of generality that the square at $(0,0)$ is white. We ...
10
votes
0answers
121 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}?$$ ...
9
votes
0answers
217 views

What is the shape of the convex $n$-gon which gives the maximum of a function?

Supposing that the length of every edge of the convex $n$-gon $P_1P_2$$\cdots$$P_n$ is 1, what is the shape of the $n$-gon which gives the maximum of the following function $A_n$? ...
6
votes
0answers
214 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 ...
5
votes
0answers
36 views

Plane tesselation, using stairs $n\times n$, is it possible?

The other day I was constructing new mathematical problems for my pupils and thought of something like this: Given the infinite sequence of "stairs" $n\times n$, constructed from $1\times1$ ...
5
votes
0answers
83 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 ...
5
votes
0answers
107 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 ...
5
votes
0answers
264 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
171 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
83 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 ...
4
votes
0answers
47 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$. ...
4
votes
0answers
96 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 ...
4
votes
0answers
125 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 ...
3
votes
0answers
24 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
25 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
111 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
22 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 ...
3
votes
0answers
109 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 ...
3
votes
0answers
94 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]
3
votes
0answers
53 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
58 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
300 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 ...
3
votes
0answers
47 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$, ...
2
votes
0answers
17 views

Number of simplices of convex hull of points on a $d$-sphere.

I was discussing this with my professor the other day and he left me to figure out. And I can't for the life of me, figure out why this is so. I would appreciate what I should look into rather than an ...
2
votes
0answers
42 views

A circle can include all but one of n points, but which one can it be?

The answers to the question "Circle enclosing all but one of n points" demonstrate that, given $n$ points, it is possible to construct a circle such that all but one of the points is inside the circle ...
2
votes
0answers
23 views

Triangulations of combinatorially equivalent polytopes

I am wondering which relation(s) there are between triangulations of combinatorially equivalent polytopes that use no new points: Let $P,Q$ be a $n$-polytopes such that their face lattices are ...
2
votes
0answers
22 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 ...
2
votes
0answers
46 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 ...
2
votes
0answers
49 views

Points on the circle

We have $n$ points on the unit circle. What is the best configuration if we want to maximize the sum of the pairwise distances of the given points?
2
votes
0answers
31 views

Number of connected sets intersecting a given set in $\mathbb{Z}^d$

Let $A \subset \mathbb{Z}^d$ and let $|A|$ be its cardinality. Let $F_n(A)$ be the number of connected sets of $\mathbb{Z}^d$ having cardinality $n$ and intersecting $A$ in at least one site. Assume ...
2
votes
0answers
44 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 ...
2
votes
0answers
56 views

Maximum number of edges in a subgraph of hypercube

Let $H_n$ is an $n$-dimensional hypercube, $|V(H_n)|=2^n, |E(H_n)|=n2^{n-1}$. Let $M\subset V(H_n), |M|=2^k, 1\le k<n$, and $G_M$ is a subgraph of $H_n$ induced by $M$, $V(G_M)=2^k$. Prove that ...
2
votes
0answers
41 views

An art gallery problem

An art gallery has the shape of a simple $n$-gon. Find the minimum number of watchmen needed to survey the building, no matter how complicated its shape be. I failed to solve the problem. Please help ...
2
votes
0answers
63 views

Fill a rectangle with squares

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

Neighbor-full partition of $\{0,1\}^n$

What is the partition of $\{0,1\}^n$ with each set connected and neighboring each other that has the maximum number of elements? (which we call $k(n)$) We say $A$ and $B$ are neighbors if their ...
2
votes
0answers
81 views

Is it possible to choose 10 points from 20000 with that property?

A set of $20000$ points is chosen in a ball of radius $6$ in $ \mathbb{R}^3 $. Do there exist $10$ ones of these points s. t. all the distances between them are less than or equal to $1$?
2
votes
0answers
67 views

Why is unit circle not sufficient to bound the partial sums?

I want to find vectors $\textbf{v}_1, \dots,\textbf{v}_n$ in $\mathbb{R}^2$ with that $\sum_{i=1}^n\textbf{v}_i=\textbf{0}$ and $\Vert \textbf{v}_i\Vert\leq 1$ for all $i=1,\dots,n$, such that for ...
2
votes
0answers
101 views

Number of Points Inside a Rectangle

This question is from a Japanese contest: Let $S$ be a set of 2002 points in the coordinate plane, no two of which have the same $x$- or $y$- coordinate. For any two points $P,Q$ in $S$ consider ...
2
votes
0answers
51 views

How prove $ \frac{2}{\sqrt3}F \geq s-1 $ for convex quadrilateral?

Let $Q$ be any convex quadrilateral of area $F$ and semiperimeter $s$. Suppose that length of any diagonal of $Q$ $ \geq$ length of any side of $Q$ $\geq 1$ How prove $ \frac{2}{\sqrt3}F \geq s-1 ...
2
votes
0answers
81 views

Generalization of Minkowski's theorem

I would like to prove a generalized version of the Minkowski's theorem, but I don't quite know how to do it. Here is what I would like to prove: Let $X\subset \mathbb{R}^d$ is convex, symmetric ...
2
votes
0answers
116 views

How many cuts does it take to remove any $n$ vertices from an $m$-dimensional hypercube?

For instance, in $m=3$ dimensions (cube), the following $n=3$ corners (red) can be cut off with a minimum of $C=2$ planes (blue). (Note you are only allowed to cut off the vertices in red.) So what ...
2
votes
0answers
87 views

Configuration analogues of projective spaces?

In a configuration, each point is incident to the same number of lines and each line is incident to the same number of points. The Fano plane is a configuration, with 3 points on each line, and 3 ...
2
votes
0answers
101 views

Sorting combinations of linearly independent vectors

Given a set of $m$ vectors in $\mathbb{R}^n$ ($m > n$), sort all combinations of $n$ linearly independent vectors according to the determinant of the matrix whose columns are the $n$ vectors. ...
2
votes
0answers
78 views

Does anyone know any specific example of such point set

Does anyone know any specific or explicit example of a set of $256$ points so that no $10$ are the vertices of a convex $10$-gon? Thanks in advance.
2
votes
0answers
137 views

A question related to Helly's Theorem on convex sets

I have one question related to differential geometry. Initilally, I am giving some background and my question is after that. Helly's Theorem Let C be a finite family of convex sets in $R^n$ such ...
2
votes
0answers
194 views

Minimum number of circles in a rectangle with no line in rectangle not intersecting any of them

Suppose we have a rectangle with sides $a$ and $b$, $a<b$, $a,b \in \mathbb R$. What is the minimum number of circles centered in the rectangle with radius $1$ such that each line passing through ...
1
vote
0answers
63 views

Circumscribed Simple Line Arrangements Have Hamiltonian Circuits?

An arrangement of $s$ lines are drawn in the plane so that no three lines intersect at a common point and no two lines are parallel. Now circumscribe this arrangement by a circle so that all ...
1
vote
0answers
8 views

Projection onto a symplex

Suppose we have $n$ vectors in an $m$-dimensional vector space such that their span is all the space and none of them are zero. We choose any hyperplane which does not pass through zero and project ...