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

2
votes
0answers
20 views

partition of convex n-gon with triangles.

A convex $n$-gon is partitioned into $n-2$ triangles with non-intersecting diagonals. For each vertex of the original polygon, odd number of the partitioning triangles share that vertex. Is it ...
2
votes
0answers
14 views

Reflection to get within convex polygon

Let $P$ be a convex polygon, and let $A_1$ be a point on the same plane as $P$. Prove that we can find an integer $n$, and points $A_2,A_3,\ldots,A_n$, such that $A_{i+1}$ is a reflection of $A_i$ ...
1
vote
0answers
44 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
35 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
28 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 ...
3
votes
1answer
24 views

Getting out of a convex forest

This problem is giving me the hardest time: Alex is lost in a forest. The forest area has a convex shape whose area is $P$. Prove that Alex can choose a path not longer than $\sqrt{2 \pi P}$ such ...
3
votes
1answer
54 views

Why is this proof that the distance between two of any five points in a square $\geq \frac{\sqrt{2}}{2}$ wrong?

Why is this proof that the distance between two of any five points in a square $\geq \frac{\sqrt{2}}{2}$ wrong? This is (again) from Zeitz. The proof is somewhat like this: let us place four of the ...
2
votes
1answer
165 views

How to divide a $4\times 4$ square in six pieces to show that from any seven points in the square, there are two at most $\sqrt 5$ apart?

Let $R$ be a $4 \times 4$ square. For any seven points on $R$, there exists at least two of them, namely $\{A,B\}$, with $d(A,B)\le\sqrt{5}.$ (Old problem): If $R$ is a rectangular region ...
1
vote
0answers
33 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
1answer
73 views

Can a Square be completely filled by smaller squares when none of the smaller squares have same area?

Can a Square $S$ be completely filled by smaller squares $S_i$ when area of $S_i \neq S_j$ whenever $i \neq j$? PS:The image is only meant to clarify the complete filling of squares otherwise it ...
2
votes
0answers
45 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 ...
2
votes
1answer
36 views

Finite projective planes

How big a set of points in general position (i.e., no three collinear) can be found in a finite projective plane of order $n$? I hope the answers won't be too technical, as I know almost nothing ...
0
votes
0answers
18 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 ...
0
votes
0answers
27 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 ...
1
vote
0answers
21 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 ...
0
votes
0answers
24 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
1answer
30 views

Convex set of points

Let $n\ge 3$ be an integer. Let $S$ be the set of $n$ points in the plane such that they are not vertices of a convex polygon, and no three are collinear. Prove that there is a triangle with vertices ...
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 ...
12
votes
1answer
297 views

Packing an infinite sequence of disks

Let $a > 1$ and $Q(a)$ denote the supremum of values of $q$ such that a countably infinite collection of disks, whose areas form an infinitely decreasing geometric progression with the start value ...
1
vote
1answer
56 views

Carathéodory's convex hulls theorem and Radon partitions

Wikipedia's article about Radon's theorem and its related states: Carathéodory's theorem states that any point in the convex hull of some set of points is also within the convex hull of a subset ...
2
votes
1answer
54 views

Polygon on the cartesian plane

In the Cartesian plane is given a polygon $\mathcal{P}$ whose vertices have integer coordinates and with sides parallel to the coordinate axes. Show that if the length of each edge of $\mathcal{P}$ is ...
0
votes
0answers
25 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 ...
1
vote
0answers
22 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$, ...
0
votes
0answers
8 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 ...
5
votes
0answers
47 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 ...
0
votes
0answers
16 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 ...
1
vote
0answers
51 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
1answer
51 views

Counting sum of lattice points

Assume a set $S$ with $|S|$ entries. Indeed, $S$ is the set of lattice points inside a $k$-sphere. Assume $V=S\oplus S$ where $\oplus$ is the Minkowski sum of two sets. Do you know any lower bound on ...
6
votes
2answers
149 views

Squaring the plane, with consecutive integer squares. And a related arrangement

Q1. I was fiddling around with squaring-the-square type algebraic maths, and came up with a family of arrangements of $n^2$ squares, with sides $1, 2, 3\ldots n^2$ ($n$ odd). Which seems like it would ...
0
votes
1answer
21 views

Connectedness of combinatorial complexes with no free faces

I'm currently reading the paper "$\mathcal{VH}$ complexes, towers and subgroups of $F \times F$" by Bridson & Wise. There they define combinatorial complexes as follows: A continous map between ...
0
votes
2answers
42 views

Notion of a concave function and proving ln is concave

I've just checked that the definition is right, a function is convex if: $(1-t)f(x_1)+tf(x_2)\ge f((1-t)x_1+tx_2)$ which is odd because this is ... well I was taught (very young age) that concave ...
2
votes
1answer
102 views

Geometry textbook

I am planning to take a graduate Geometry course next semester. The preliminary syllabus does not specify any textbook but has the following descriptions: Catalog Course Description: This course ...
3
votes
1answer
97 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 ...
1
vote
1answer
46 views

Bridge Number , Knot Theory

I had been reading some knot theory lately and got to know about a whole classification of 2-bridge knots , does their exist any such extensive study over 3-bridge knots?
5
votes
0answers
111 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 ...
1
vote
4answers
2k views

What is the maximum number of pieces that a pizza can be cut into by 7 knife cuts? (NBHM 2005)

I am seeing this question very first time and do not know any formal way to solve it. Which part of mathematics it is related to? What is the maximum number of pieces that a pizza can be cut into by ...
1
vote
1answer
84 views

How many regions are created by the set of all hyperplanes defined by a set of points?

If we have a set of points X in d-dimensional euclidean space, and we look at the set of all n-dimensional hyperplanes that are defined by any subset Y of X (in the sense of being the unique ...
2
votes
3answers
85 views

Separating $3n$ points on the plane by a line

I am trying to solve a problem in geometry (a contest-type question), and I wondering if the following result is true. (If it is true, then it makes life much easier!) Suppose there are $3n$ ...
3
votes
0answers
90 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 ...
4
votes
0answers
43 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 ...
1
vote
2answers
38 views

How many marbles must be placed in a square area of $16 in^2$ to ensure that two of the marbles are within $2 \sqrt{2}$ inches of each other?

How many marbles must be placed in a square area of $16 in^2$ to ensure that two of the marbles are within $2 \sqrt{2}$ inches of each other? Wouldn't even know how to begin this question.
0
votes
1answer
53 views

A combinatorial action of a discrete group is proper if and only if it has finite vertex stabilizers

First, let me fix some definitions. The action of a group $G$ on a topological space $X$ is proper if for every compact subspace $K \subseteq X$ the set $\{g \in G \ | \ g K \cap K \neq\varnothing ...
11
votes
2answers
287 views

Unit diameter pentagons with maximum area

In the euclidean plane, if one considers the set of quadrilaterals having unit diameter (maximum distance between two points in the convex envelope), it is quite easy to give a description of the ...
13
votes
1answer
111 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 ...
2
votes
0answers
51 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 ...
10
votes
0answers
111 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 ...
25
votes
3answers
517 views

Expected length of the shortest polygonal path connecting random points

$N$ points are selected in a uniformly distributed random way in a disk of a unit radius. Let $L(N)$ denote the expected length of the shortest polygonal path that visits each of the points at least ...
2
votes
1answer
42 views

Marking the point closest to each point

We have $6000$ points in the plane. All distances between every pair of them are distinct. For each point, we mark red the point nearest to it. What is the smallest number of points that can be marked ...
4
votes
0answers
114 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 ...
35
votes
2answers
2k views

Cutting up a circle to make a square

We know that there is no paper-and-scissors solution to Tarski's circle-squaring problem (my six-year-old daughter told me this while eating lunch one day) but what are the closest approximations, if ...