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

0
votes
0answers
4 views

Example of an hyperplane arrangement whose bounded region is not star-shaped

Could anyone provide an example of an (essential) hyperplane arrangement whose bounded region is not star-shaped? (Appears as exercise 4.29 in "Oriented Matroids". Hint: six lines in the plane are ...
3
votes
0answers
20 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 ...
0
votes
0answers
30 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
2answers
23 views

Every circle passes through points of all colors

Let $n$ be a positive integer. Is it possible to color every point in the plane in one of $n$ colors so that every (nondegenerate) circle contains points of every color? If we can do the coloring so ...
3
votes
1answer
42 views

Inequality between area and boundary length, $4\pi A \leq L^2 $

Suppose we have a simply connected region $R$ in $\mathbb{R}^2$ with area $A$ and the boundary of $R$ is a curve sufficiently well behaved (say piecewise $C^1$) that we can say it has length $L$. Then ...
4
votes
1answer
95 views

Cutting a pie with a fork

You baked a pie in the shape of a disc, with some cherries spread unevenly on its top. You want to give each of your two children a piece of cake such that: The pieces are congruent - have the same ...
0
votes
1answer
46 views

Beautiful Problem about pairwisely non-similar n-gons.

Let n be an integer (n>2). Show that there exists an infinite number of pairwisely non-similar inscribed n-gons, lengths of all sides and diagonals and areas of each of which are integers. My ...
1
vote
1answer
31 views

How to determine if the given points form a convex irregular Hexagon.

Say I have a collection of points (x,y). From the given points, I want to determine if it forms a convex irregular Hexagon. My goal is to determine that the points I have gathered form an irregular ...
1
vote
1answer
40 views

Arrange 10 points on five lines where each line(intersecting) has exactly 4 points

One possible case is that forming a star and then arranging 10 points on its vertices. Is there any other possible case for this arrangement? If not then how can we prove it mathematically? ...
1
vote
0answers
30 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 ...
0
votes
1answer
14 views

Relating maximal elements of downsets to minimal elements of the complement

Denote by $\mathcal{P}(S)$ the set of non-empty subsets of a finite $S$. Suppose that $A\subset \mathcal{P}(S)$ is a downset, i.e., every subset $Q$ of any $P\in A$ is also contained in $A$. We can ...
4
votes
0answers
33 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$. ...
2
votes
1answer
23 views

Polygons with fixed number of axes of symmetry

Let $k$ be a positive integer. Suppose a polygon has exactly $k$ axes of symmetry. How many sides may the polygon have? A regular $n$-gon has $n$ axes of symmetry, so one answer is $k$. What are ...
4
votes
1answer
29 views

Repeated projection of points onto lines

Consider a point $P$ on the Euclidean plane, and lines $l_1,l_2,\ldots,l_n$. Project $P$ onto $l_1$. Then project the resulting point onto $l_2$. Then project the resulting point onto $l_3$, and so ...
5
votes
1answer
111 views

Partition rectangle into finite number of squares

For what positive real numbers $x,y$ can an $x\times y$ rectangle be partitioned into a finite number of squares? When $\dfrac{x}{y}$ is a rational number, it is not hard to see that we can partition ...
0
votes
3answers
29 views

Is there a theorem or axiom which shows that permutations of step sequences through a lattice graph result in the same destination?

I have been searching for a theorem, lemma, or even an axiom which shows that the permutations of a step sequence in Taxicab Geometry result in the same destination in such a lattice graph. To ...
11
votes
2answers
149 views

Partitioning the plane into three sets each intersecting the vertices of every square with side 1?

Q1. Is it possible to partition the plane into three sets such that each of them contains at least one vertex of every square with side 1 ? (I mean all squares of side-length 1, not just those with ...
5
votes
1answer
60 views

Bounded area for any triangle formed by polygons

Let $P_1,P_2,P_3$ be closed polygons on the plane. Suppose that for any points $A\in P_1$ (meaning $A$ can be inside or on the boudary of $P_1$), $B\in P_2,C\in P_3$, we have $[ABC]\leq 1$. Is it ...
3
votes
0answers
41 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]
8
votes
0answers
43 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}?$$ ...
2
votes
1answer
77 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
19 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
46 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
37 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
31 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
26 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
59 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
172 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
34 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
77 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
46 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
1answer
47 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
23 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
31 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
332 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
65 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
27 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
10 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
54 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
52 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
156 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
22 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 ...