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
6 views

Arrangement of Convex Discs in the plane is independent of the choice of origin?

This is the Problem 3.1 in 'Combinatorial Geometry' by J. Pach, and P. Agarwal. Problem: Prove that if C is any arrangement of convex discs in the plane, then $\bar{d}$$(C,\mathbb{R}^2)$ and ...
1
vote
0answers
7 views

Number of translated cubes covering a given hypercube in $\mathbb{R}^n$

Let $\Omega \subset \mathbb{R}^n$ be open and bounded, and let $Q \subset \Omega$ be a hypercube. Furthermore, denote by $D$ the $n$-dimensional unit cube $(0,1)^n$. Let $k \in \mathbb{N}$ be big, ...
2
votes
1answer
19 views

Barycentric subdivisions and labeling of $(d-1)$-simplex

I am trying to prove that it is always possible to label the vertices of the $k$-th barycentric subdivision of a $(d −1)$-dimensional simplex with labels $1, 2, . . . , d$ such that each simplex ...
1
vote
0answers
32 views

Given $5$ points on a sphere, divide the surface into $5$ congruent connected regions containing one point.

There are $5$ points on the surface of a sphere. Is it always possible to divide the surface into $5$ connected congruent regions such that each region contains one of the $5$ points?
2
votes
0answers
19 views

Triangulations of combinatorially equivalent polytopes

I am wondering which relation(s) there are between triangulations of combinatorially equivalent polytopes that use no new points: Let $P,Q$ be a $n$-polytopes such that their face lattices are ...
2
votes
0answers
19 views

Hexagons share interior points

Can we draw infinitely many hexagons, not necessarily convex, on the plane so that any three of them share a common interior point, but no four of them does? For four hexagons this is possible, using ...
3
votes
1answer
305 views

Positivity of the alternating sum associated to at most five subspaces

Let $V_1 , V_2 , \dots , V_n $ be proper subspaces of $ \mathbb{C}^m$ and let $$\alpha = \sum_{r=1}^n (-1)^{r+1} \sum_{ \ i_1 < i_2 < \cdots < i_r } dim(V_{i_1} \cap \cdots \cap V_{i_r})$$ ...
1
vote
0answers
33 views

Variation of the opaque forest problem (a.k.a farmyard problem)

I was wondering about the following variation of the opaque forest problem (see here and there for previous questions) : What is the least length set of segments that will intersect every straight ...
1
vote
0answers
19 views

Projection of hyper-cubes via multiple variable elimination

I am not a mathematician but I do use some tools from geometry in robotics. So, I apologize if what I am writing here is not mathematically consistent but I really do need your help. I have a linear ...
1
vote
2answers
171 views

Similar Triangles in Tiling a Plane

When tiling the infinite plane with triangles, is it necessary for two of the triangles to be similar? I've tried different methods to construct, but none work. My idea was to use right triangles to ...
3
votes
0answers
36 views

Fill unit square in Euclid plane [closed]

Assume $A,B$ are two subset of $\mathbb{Z^2}$. In addition, $A$ is finite. Satisfies: i) For all $a_1,a_2 \in A$ and $b_1,b_2 \in B$ , $a_1+b_1=a_2+b_2$ implies $a_1=a_2$ and $b_1=b_2$ ii) ...
3
votes
1answer
57 views

Triangle with same black and white areas

Suppose we have an infinite chessboard with the usual black/white coloring. A triangle $T$ with area $a$ is given with vertices at corners of some cells. Prove that there exists another triangle $T'$ ...
7
votes
1answer
44 views

Number of lines formed by sides of polygon

Let $n\geq 3$, and consider an $n$-gon, not necessarily convex. What is the minimum number of distinct lines that are formed by sides of the $n$-gon? When $n=3,4,5$ the answer is $3,4,5$ ...
0
votes
0answers
12 views

Proof for non-tetrahydralizability of Schonhardt polyhedron

It is established that not all polyhedrons are tetrahydralizable. Schonhardt's polyhedron is the simplest example for it. I was reading the proof for this given in the book "Art Gallery Theorems and ...
1
vote
1answer
18 views

Combinatorial circle placement

Suppose we have area bound by $0\leq x\leq 2$,$0\leq y\leq 2$ We choose 17 points, there should be at least two with distance max $d\leq\frac{1}{\sqrt{2}}$ Tried to count area of ...
1
vote
1answer
51 views

To find the arrangement of given letters so that there is fixed number of transition between them.

A 10 letter word is composed of $P,\ Q,\ R,\ S$. The problem is to find the number of arrangements of these letters which could lead to a fixed number of transitions between each pair of letters. ...
5
votes
3answers
106 views

Locked convex polyhedra

Call a set of polyhedra free if it is possible to rigidly move the polyhedra, without any polyhedron intersecting any other, so that their pairwise distances are arbitrary large, and locked otherwise. ...
0
votes
0answers
25 views

Monochromatic triangle in two closed set which cover the plane

I am reading Section on Euclidean Ramsey Theory in Ronald Graham's Rudiments of Ramsey Theory. Exercise 7.3 states that Show that if $E^2$ is covered by two closed sets of colors then every ...
1
vote
0answers
33 views

What is the optimal tiling of a regular n-gon in the plane?

I want to tile the plane with equal-sized regular polygons of $n$ sides. Obviously for some $n$, the tiles will be able to tessellate and cover the whole plane (e.g triangles, squares, hexagons) I ...
1
vote
0answers
18 views

Segments Containing Lattice Points

Prove that any finite set $H$ of lattice points on the plane has a subset $K$ with the following properties: any vertical or horizontal line in the plane cuts $K$ in at most $2$ points, any point of ...
9
votes
2answers
184 views

Tiling of a $9\times 7$ rectangle

Can a rectangle $9\times 7$ be tiled by "L-blocks" (an L-block consists of $3$ unit squares)? Although the problem seems to be easy, coloring didn't help me. The general theory is interesting, but ...
0
votes
1answer
45 views

Minimum number of straight lines needed to cover $n$ points

Suppose we are given a set of $n$ points in the euclidean plane , they are distributed arbitarily (not in general position). what is the minimum number of lines in the plane needed to cover them all?
3
votes
1answer
49 views

How many shapes are possible from gluing together the faces of n cubes?

Say I have n cubes. I am allowed to glue the faces of these cubes together, but the faces must line up perfectly. How many unique shapes could I make? All orientations of one shape are considered to ...
0
votes
0answers
26 views

On the base axioms of a matroid

The base axioms of a matroid state that A collection $B\subseteq 2^E$ is a set of bases of a matroid M(E,I) if and only if the following hold B1: $B\neq \emptyset$ B2: If $B_1,B_2\in B$ and $x\in ...
2
votes
1answer
88 views

Proof involving Ramsey numbers

$S$ is a set of R(m,m;3) points in the plane in which no 3 points are collinear. I am trying to prove that $S$ contains $m$ points that form a convex $m$-gon. I have tried using similar logic to the ...
4
votes
2answers
67 views

IMO 1997 problem 1

In the plane the points with integer coordinates are the vertices of unit squares. The squares are colored alternately black and white (as on a chessboard). For any pair of positive integers $m$ and ...
1
vote
1answer
31 views

How to show that for the Schläfli symbol$\{m,k\}$ the polygon is non-degenerate if $m$ and $k$ are coprime?

I know by definition that when the elements of the Schläfli symbol $\{m,k\}$ are coprime then the polygon is non-degenerate, i.e. can be traced without lifting a pencil off of the paper. Is it ...
2
votes
0answers
44 views

Points on the circle

We have $n$ points on the unit circle. What is the best configuration if we want to maximize the sum of the pairwise distances of the given points?
1
vote
2answers
182 views

Generating function for number of different tessellation checkered rectangle

Let $R_n$ be checkered rectangle sized $n \times 4, n \ge 1$. Let $a_n$ be number of different $R_n$ tiling with rectangles sized $1 \times 3$. $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ ...
-2
votes
3answers
145 views

Two questions about eulerian and hamiltonian graphs.

I have 2 questions in graph theory. $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $Graph\ 1$ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $Graph\ 2$ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ ...
1
vote
0answers
45 views

Minimal diagonal intersections in a convex polygon

OEIS A006561 gives the number of intersection points in the diagonals of a regular polygon. There's a paper by Poonen. For 4 vertices to 12, the number of intersection points is: $$1, 5, 13, 35, 49, ...
4
votes
1answer
56 views

Cycles of equally spaced points on a circle

Take $n$ equally spaced points on a circle. Connect them by a cycle(circuit) with $n$ line segments. Two cycles are considered equivalent if same when rotated or reflected. How many cycles are there? ...
1
vote
1answer
35 views

Finding Minimum Weight Subgraph Spanning Tree

Suppose we have a graph $G = (V, E, w:e\in E \to x \in \{0,1\})$. That is, a set of vertices, a set of edges and a weight function that assigns edges weights of 0 or 1. Suppose we also have a subset ...
2
votes
1answer
62 views

Choose $3n$ points on a circle, show that there are two diametrically opposite point

On a circle of length $6n$, we choose $3n$ points such that they split the circle into $n$ arcs of length 1, $n$ arcs of length 2, $n$ arcs of length 3. Show that there exists two chosen points which ...
1
vote
1answer
63 views

How similar can the nets of distinct polyhedra be?

My school, and most math books do not cover 3-d geometry well, especially the topics of polyhedron nets. However, I see quite a few questions here are being answered about them. I was wondering about ...
0
votes
0answers
140 views

Projection of hybercube without Fourier-Motzkin Elimination

I am not a mathematician but I do use some tools from geometry in robotics. So, I apologize if what I am writing here is not mathematically consistent but I really do need your help. I have a linear ...
2
votes
0answers
30 views

Number of connected sets intersecting a given set in $\mathbb{Z}^d$

Let $A \subset \mathbb{Z}^d$ and let $|A|$ be its cardinality. Let $F_n(A)$ be the number of connected sets of $\mathbb{Z}^d$ having cardinality $n$ and intersecting $A$ in at least one site. Assume ...
4
votes
0answers
73 views

Affine-regular hexagon in convex body

An affine-regular $n$-gon is a non-degenerate affine image of the regular $n$-gon. It seems to be a standard fact in combinatorial geometry that inside every convex compact set $K\subseteq \mathbb ...
0
votes
1answer
102 views

Tiling a rectangle with L-tromino [duplicate]

Consider a $2^{1999} \times 2^{1999}$ square, with a single $1 \times 1$ square removed. Show that no matter where the small square is removed it is possible to tile this "giant square minus tiny ...
3
votes
0answers
25 views

Maximum overlap of two convex bodies

Let $\Delta_n=\big\{(x_1,x_2,\ldots,x_n): \sum_i x_i \leq 1, x_i \geq 0\big\}$ denote an n-dimensional simplex. I am trying to find an $y \in \mathbb{R}^n$ such that the $y-$shifted negative simplex ...
2
votes
1answer
43 views

Definite shape of polyominos

I'm currently exploring polyominoes and there's this question I'm pondering on. It said, "how can you convince yourself that a new shape is really 'different' from those already obtained?". I know ...
-2
votes
2answers
229 views

Tiling problem: 100 by 100 grid and 1 by 8 pieces

Why can't I tile a $100 \times 100$ table with $1$ by $8$ pieces? If we look at the number of tiles, $100^2$ is divisible by $8$. So this does not contradict existence of such tiling. The standard ...
2
votes
0answers
43 views

Center of mass of vertices without enumeration?

Given a $n$-dimensional convex polytope defined by $A x\leq b$ and $A_{eq} x = b_{eq}$, is there an efficient way to determine the average coordinates of all vertices without enumerating them? (As if ...
4
votes
1answer
45 views

Combinatorial problem of choosing points inside an equilateral triangle without them being too close.

Determine the smallest integer $m_n$ which satisfies the following property: If $m_n$ points are chosen inside an equilateral triangle of sides 1, then at least two of them are at distance ...
3
votes
0answers
102 views

Trajectories on a circular billiards table

This question is related to The case of Captain America's shield: a variation of Alhazen's Billard problem, but more focused. Let the unit disc in the plane be our billiards table, and let $C$ ...
3
votes
0answers
22 views

Existence of fair parallel queues

I just spent a few days at a major theme park. The queue for one particular ride (involving pirates) bifurcated upon entry; the two sides wound independently through a maze and emerged next to each ...
4
votes
2answers
87 views

Self-avoiding rook walks on small rectangular chessboards (contest question)

I am not sure how to get a closed-form formula for $R(3,n)$ as the recursion involves a summation. Maybe the best that can be achieved is a recursion that does not involve a summation having an upper ...
3
votes
1answer
74 views

Intersection of Random Subspace and Hypercube

Suppose that $A \subset \mathbb{R}^n$ is a random linear subspace of dimension $k < n$. I am interested in the event that $A$ intersects the hypercube $[-1,\ 1]^n$ at a specific face. In other ...
1
vote
2answers
190 views

Building a box from smaller boxes

John has 77 boxes each having dimensions 3x3x1. Is it possible for John to build one big box with dimensions 7x9x11? I'm leaning towards no, but I would like others opinion.
15
votes
1answer
280 views

Hypercube and Hyperspheres

Let $n,k\in\mathbb{N}$. In this problem, the geometry of $\mathbb{R}^n$ is the usual Euclidean geometry. The lattice hypercube $ Q(n,k)$ is defined to be the set $ \{1,2,...,k\}^n ...