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
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 ...
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
1answer
21 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
17 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 ...
11
votes
1answer
281 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
33 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
46 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
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 ...
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$, ...
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 ...
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 ...
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 ...
1
vote
0answers
43 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
43 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
130 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
20 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
26 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
80 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
80 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
45 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?
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 ...
1
vote
4answers
705 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
69 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
79 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
78 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
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 ...
1
vote
2answers
35 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
50 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 ...
10
votes
2answers
264 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 ...
11
votes
1answer
94 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
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 ...
9
votes
0answers
99 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
496 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
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 ...
32
votes
2answers
1k 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 ...
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 ...
9
votes
1answer
106 views

Minimum number of hemispheres covering a sphere

Here is a question which seems easy but seems to have many pitfalls. If I give you an arbitrary covering of the sphere by $N$ closed hemispheres. You can pick any of the hemispheres to keep. What is ...
4
votes
2answers
106 views

Convex sets: a hint on how to solve a problem

Could anyone give me a hint on how to solve the following problem? Let $X_1, \dots, X_{d+1}$ be some finite sets in $\mathbb{R}^d$, such that the origin lies in ${\rm conv}(X_i)$ for all $i \in \{1, ...
1
vote
2answers
72 views

Dicrete Math Interesting question about Tromino

Prove that for a m$\times$n rectangle, if this rectangle can be covered completely by trominoes of the shape indicated in the picture, then mn is divisible by 3. I came up with a tentative way to ...
5
votes
6answers
299 views

Covering a chess board with $2$ missing places with $31$ dominoes

I am reading a book that is intended to a wide audience (and not just mathematicians etc'), the book is, of course, about mathematics (Its still not clear about what exactly, I am only in page $2$). ...
6
votes
1answer
263 views

Minimum number of lines covering n points

Let there be n points in the plane. I want to know the minimum number of horizontal and vertical lines covering all the points in the plane. My initial approach started like this, 1) for each point I ...
8
votes
1answer
145 views

Is this curve the circumference of a circle?

Let $\Gamma$ be a single closed curve with no self-intersections on a plane which satisfies the following condition : Condition : For any distinct four points $P, Q, R, S$ on $\Gamma$, if the line ...
4
votes
2answers
161 views

An Olympiad Problem (tiling a rectangle with the L-tetromino)

An L block that is 3 unit blocks high and 2 unit blocks wide . It is true that if an n by m rectangle can be covered by such L blocks with out overlap that we would require an even amount of L blocks, ...
0
votes
1answer
211 views

Set of points in the plane which is intersected by every line on the plane and in which no more than K points are collinear

Question Let $K \in \mathbb{N} (K \geq 3)$ and $r \in \mathbb{R}^+$. Either find a set $S$ of points in the plane such that every line on the plane intersects atleast one point in $S$ and ...
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 ...
1
vote
1answer
24 views

Choosing vectors on a complex sphere

Consider a complex $t$ dimensional unit sphere. Say we pick $n$ points on this with inner products in the set $\{a_1,a_2,\dots,a_r\}$ (we have $n$ inner products with value $1$). Note the set ...
1
vote
1answer
975 views

How many circles of radius r fit in a single bigger circle of radius R?

Is there any formula to calculate how many circles of radius r fit in a single bigger circle of radius R? I'd apreciate if it didn't involve advanced math, like calculus (unless there is no other way, ...
0
votes
1answer
90 views

Question related to Desargues' Theorem

The diagram below is one way of drawing two triangles ($\Delta PQR,\ \Delta P'Q'R'$) perspective from a point ($O$), with pairs of corresponding sides meeting at $D, E, F$ as in Desargues' Theorem ...
3
votes
0answers
107 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 ...