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

18
votes
0answers
211 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
128 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 ...
8
votes
0answers
49 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}?$$ ...
7
votes
0answers
172 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
174 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
62 views

How many unit squares can overlap a given unit square without overlapping each other?

How many unit squares can overlap a given unit square without overlapping each other? @calculus has managed to arrange 7 squares (see this GeogebraTube page). This seems like the maximum ...
5
votes
0answers
53 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
135 views

How many points you should draw in the square at least?

There is a square, which side length is $2$, To ensure there exists a triangle in the square, with an area less than $0.5$, how many points should you draw in the square at least. the goal is for all ...
5
votes
0answers
52 views

The largest regular m-gon that fits inside a regular n-gon

This question just popped into my head while doing some "for fun" math. More precisely: Let $m,n\in\Bbb{Z};m,n>2$. Let $P$ be a regular $n$-gon (let's say $P$ is the convex hull of the $n$ $n$th ...
5
votes
0answers
166 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
36 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
85 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
114 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
92 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
38 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
55 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
52 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
184 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
295 views

Squaring rectangles

it is a nice high-school exercise to prove that a square can be tiled with n squares if and only if n=1, 4 or is any integer greater or equal to 6. A direct consequence is that any rectangle that can ...
3
votes
0answers
185 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 ...
3
votes
0answers
46 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
60 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
39 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 ...
2
votes
0answers
60 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
94 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
69 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
95 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
76 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
126 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
178 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
22 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
18 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?
1
vote
0answers
28 views

How many 100 sq km bounding boxes cover the surface are of the earth.

I need to figure out how many 100 square km bounding boxes cover the surface area of the earth. I'm trying to use the Instagram API to download data. Their API supports a lat/long with a maximum ...
1
vote
0answers
42 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 ...
1
vote
0answers
37 views

Determine the formula for hexagon arrangements.

The puzzle to be solved is similar to a jigsaw but using n regular hexagons of equal size for pieces. The pieces are to be placed within a defined perimeter to create a picture. Q: If we let the ...
1
vote
0answers
47 views

Number of vectors which are $\alpha$ angle apart

Let, $A\subseteq\{z=(z_1,z_2)\in\mathbb{C}^2:|z|^2=|z_1|^2+|z_2|^2=1\}$ such that any two vectors in $A$ have angle between them $\ge\alpha$ for some $0<\alpha<1$. I want to prove that ...
1
vote
0answers
43 views

The number of lattice triangle subdivision.

Let $L_{m,n} \subset \mathbb{R}^2$ be a rectangle given by $[m,0]\times[0,n]$ with $m,n$ positive integers. Define $N(m,n)$ to be the number of subdivisions of $L_{m,n}$ into lattice triangles of area ...
1
vote
0answers
35 views

Mid-points of all sides and diagonals of a regular 2014-gon

This is an interesting problem I came across: In a regular 2014-gon, all mid-points of all sides and diagonals are marked. What is the maximal number of such points that belong to a same ...
1
vote
0answers
27 views

minimum number of unit distances required for a unit equilateral triangle

Problem. Suppose we have $n$ points on the plane. Among $\binom{n}{2}$ pairwise distances, there are $e$ number of unit distances. Find minimum $e$ ($e$ as a function of $n$) so that there is a ...
1
vote
0answers
20 views

Polygonal disks

Consider the closed polygonal discs $P_1$, $P_2$, $P_3$ with the property that for any three points $A\in P_1$, $B\in P_2$, $C\in P_3$, we have $[\triangle ABC]\le 1$. (Here $[X]$ denotes the area of ...
1
vote
0answers
25 views

Szemeredi Trotter and additive combinatorics on A+AA

I am trying to get a lower bound on $|A+AA|$ where $A$ is a set, and $A+AA=\{a+bc: a,b,c \in A\}$ using Szemeredi Trotter. I would think we need to form lines of the form $y=ax+b$ where $a,b \in A$, ...
1
vote
0answers
57 views

Numbers of $m$-simplices in the barycentric subdivision of an $n$-simplex ($m \leq n$).

Can someone indicate me how to count the numbers of $m$-simplices in the barycentric subdivision of an $n$-simplex (m $\leq n$) in an efficient way? For $m = n$, I have come up with the following ...
1
vote
0answers
50 views

Fixed Length Cycle Search

I am given a list of $0 \le M \le 2n(n-1) $ edges of a graph. My goal is to find a connected subgraph of this graph such that the degree of every vertex in the subgraph is $n$ that has exactly $n$ ...
1
vote
0answers
34 views

subspace arrangement not generated by products of linear forms

Let $k$ be an algebraically closed field. A subspace arrangement in $k^d$ is a finite union of proper subspaces of $k^d$ and similarly we define an arrangement of hyperplanes. Let $A$ be a subspace ...
1
vote
0answers
38 views

Two coloured plane

Can you prove that For any two angles $θ,ϕ$ there exists a monochromatic triangle that has angles $θ,ϕ,180−(θ+ϕ)$ in two coloured plane?
1
vote
0answers
183 views

Does this hold?

Strayed on the following question. Assume that $x_{1}$,$\ldots$, $x_{d}\ge0$ with $x_{1}+\ldots+x_{d}=1$ and $y_{1},\ldots,y_{d}\in\mathbb{R}$. Does $$ \min_{1\le i\ne j\le ...
0
votes
0answers
32 views

How many regions created by lines,circles, lines and circles, ellipses, spheres, planes from cutting?

I came up with a fantastic exercise (well not so fantastic but I think its a good generalization of classic things). In each of the following cases, find (1) the maximum number of points of ...
0
votes
0answers
44 views

Combinatorial approach to calculate determinant

Suppose you have set of $n*n$ matrices with entries from the set $\{1,-1\}$. Then what can be the maximum determinant which you can obtain from such type of matrices.
0
votes
0answers
35 views

Coloring a circle

A circular spintop is colored in blue, red and green. Whenever the spintop is rotated 120 degrees, the pattern of colors looks exactly the same, only that blue becomes red, red becomes green and green ...
0
votes
0answers
20 views

Existence objective function given optimality regions

Let $I$ and $X$ be finite, nonempty sets, and denote by $\Delta(X)$ the set of probability measures on $(X,2^X)$. Suppose that for each $i \in I$, we are given a subset $M_i \subseteq \Delta(X)$ of ...