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

1
vote
2answers
53 views

Choosing sets of vectors on a complex sphere

Consider a complex $t$ dimensional unit sphere. Can we have $t$ sets of $2^t$ vectors $v_{ij}\in \Bbb C^t$ on the sphere where $i=1$ to $t$ and $j=1$ to $2^t$ on this with inner products satisfying ...
11
votes
1answer
96 views

Expected values of some properties of the convex hull of a random set of points

$N$ points are selected in a uniformly distributed random way in a disk of the unit radius. Let $P(N)$ and $A(N)$ denote the expected perimeter and the expected area of their convex hull. For what ...
3
votes
1answer
81 views

Placing n points in a MxM square grid

I am facing an apparently well-known problem: placing $n$ points in a discrete grid so that the points are 'evenly' distributed. By evenly I mean that I would like the density of points to be nearly ...
3
votes
1answer
101 views

pigeonhole principle on a circle

In a disk of radius 10, how can we find all values n such that there are exactly n points in the disk and such that no matter how the n points are arranged, we can draw a disk with radius 1 in the ...
2
votes
1answer
77 views

Inner product between certain vectors on a simplex.

For $n\geq 2$, let $\Delta^n$ be a regular $n$-dimensional simplex in $\mathbb{R}^n$ centered at the origin ${\bf 0}$ and inscribed in the unit sphere $S^{n-1}$. Let ${\bf v}_0,{\bf v}_1,\ldots,{\bf ...
15
votes
0answers
151 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 ...
9
votes
0answers
100 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 ...
7
votes
0answers
152 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
93 views

Biggest Little Polyhedron

The Biggest Little Polygon problem asks for the polygon with greatest area where the largest diameter is 1. Let's add a dimension and find the largest volumes. What is the biggest little polyhedron ...
5
votes
0answers
43 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
164 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
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
95 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 ...
4
votes
0answers
42 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 ...
4
votes
0answers
97 views

Dirichlet's approximation theorem (simultaneous version): proof via Minkowski's theorem

There is a proof of the Dirichlet's approximation theorem based on Minkowski's theorem. The proof is given on wikipedia (http://en.wikipedia.org/wiki/Dirichlet%27s_approximation_theorem) and it is ...
4
votes
0answers
77 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
83 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
79 views

The Erdős-Szekeres problem on points in convex position

The Erdős-Szekeres problem on points in convex position and its proof using Ramsey theorem are well know. The problem goes like this: For every natural number $k$ there exists a number $n(k)$ such ...
3
votes
0answers
110 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
160 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
105 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
155 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
40 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
47 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
77 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
53 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
90 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
74 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
119 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
171 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
16 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
18 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
18 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
44 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
43 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
33 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
35 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
179 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
18 views

Pairs of points with distances in a convex polygon

$A$ is the set of points of a convex $n$-gon on a plane. The distinct pairwise distances between any $2$ points in $A$ arranged in descending order is $d_1>d_2>...>d_m>0$. Let the number ...
0
votes
0answers
17 views

Straight lines and lattice points

Given a positive integer $n$ and some straight lines in the plane such that none of the lines passes through $(0,0)$, and every lattice point $(a,b)$, where $ 0\leq a,b\leq n$ are integers and ...
0
votes
0answers
23 views

Space variant of problem 5 from RMM 2011

We have a finite set of points $\{A_1, ... , A_n\}$ in $d$-dimensional space such that distances from $A_i$ to all other points are just a permutation of distances from $A_j$ to all other points. For ...
0
votes
0answers
7 views

Szemeredi Trotter for points and circles of mixed radii

So the standard Szemeredi-Trotter holds for points and lines and for points and circles of a single fixed radius. That is, given a set $P$ of $N$ points and a set $L$ of $M$ (lines or circles of ...
0
votes
0answers
12 views

Conne's construction in coding a Penrose tiling seems not to universally work

In Appendix D, pp. 179 ff, of Alain Conne's "Noncommutative Geometry", www.alainconnes.orgdocsbook94bigpdf.pdf, the author looks at Penrose tilings of the plane which are composed of two types of ...
0
votes
0answers
142 views

Generalizing Euler's Polyhedral Formula for Graph Embeddings in Higher Dimensions.

In the plane, Euler's Polyhedral formula tells us that $V - E + F = \chi$, where for graph embeddings we have that $\chi = 1$. Alternatively, we can think of a graph embedding as a simplicial ...