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

22
votes
0answers
279 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 ...
12
votes
0answers
154 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
116 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}?$$ ...
8
votes
0answers
210 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
206 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
81 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
248 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
169 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
73 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
46 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
94 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
120 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 ...
4
votes
0answers
105 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
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
101 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
87 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
78 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
51 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
55 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
267 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
15 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
19 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
44 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
30 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
43 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
47 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
39 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
60 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
72 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
48 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
62 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
92 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
49 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
77 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
112 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
84 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
100 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
132 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
191 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
31 views

Variation of the opaque forest problem (a.k.a farmyard problem)

I was wondering about the following variation of the opaque forest problem (see here and there for previous questions) : What is the least length set of segments that will intersect every straight ...
1
vote
0answers
19 views

Projection of hyper-cubes via multiple variable elimination

I am not a mathematician but I do use some tools from geometry in robotics. So, I apologize if what I am writing here is not mathematically consistent but I really do need your help. I have a linear ...
1
vote
0answers
33 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 ...
1
vote
0answers
18 views

Segments Containing Lattice Points

Prove that any finite set $H$ of lattice points on the plane has a subset $K$ with the following properties: any vertical or horizontal line in the plane cuts $K$ in at most $2$ points, any point of ...
1
vote
0answers
42 views

Minimal diagonal intersections in a convex polygon

OEIS A006561 gives the number of intersection points in the diagonals of a regular polygon. There's a paper by Poonen. For 4 vertices to 12, the number of intersection points is: $$1, 5, 13, 35, 49, ...
1
vote
0answers
32 views

Lattice points-Triangle

We have a triangle $ T $ with vertices at the $ \mathbb{Z} \times \mathbb{Z} $ grid . Now, consider the surface $ 2T= \{x \in \mathbb{R}^2 : \frac{x}{2} \in T \} $ ( so, double $ T $ ). Is it possible ...
1
vote
0answers
23 views

Find largest regions bounded by a set of planes

Suppose we are given a set of planes that partition the unit cube into a large number of regions. Is there a computationally efficient way to find the region with the largest volume?