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
53 views
+50

Combinatorics problem involving n-dimensional space

Consider a set of more than $\frac {2^{n+1}} {n}$ points $(n>2)$, chosen from the $2^n$ points of the $n$-dimensional space which have the coordinates $\{ \pm1, \pm1, ..., \pm1 \}$. Show that ...
5
votes
0answers
32 views

Plane tesselation, using stairs $n\times n$, is it possible?

The other day I was constructing new mathematical problems for my pupils and thought of something like this: Given the infinite sequence of "stairs" $n\times n$, constructed from $1\times1$ ...
2
votes
0answers
15 views

Number of simplices of convex hull of points on a $d$-sphere.

I was discussing this with my professor the other day and he left me to figure out. And I can't for the life of me, figure out why this is so. I would appreciate what I should look into rather than an ...
0
votes
1answer
27 views

Combinatorial Geometry explanation

I do not understand what is going on in $(4)$: for every flat $E \in \mathcal F$, $E \ne X$, the flats that cover $E$ in $\mathcal F$ partition the remaining parts. What is meant by "the flats ...
5
votes
1answer
40 views

Maximum number of right-angled triangles

Let $S$ be a set of $n$ points in the plane, no $3$ collinear. Determine the maximum number of right-angled triangles with all three vertices as points in $S$. This is a slightly more difficult ...
0
votes
0answers
51 views
+50

Circumscribed Simple Line Arrangements Have Hamiltonian Circuits?

An arrangement of $s$ lines are drawn in the plane so that no three lines intersect at a common point and no two lines are parallel. Now circumscribe this arrangement by a circle so that all ...
1
vote
0answers
8 views

Projection onto a symplex

Suppose we have $n$ vectors in an $m$-dimensional vector space such that their span is all the space and none of them are zero. We choose any hyperplane which does not pass through zero and project ...
0
votes
0answers
16 views

Two polylines could form a convex quadrilateral

A close polyline $\Delta$ with length $n$ here means a sequence of segments $A_1A_2,\ldots, A_{n-1}A_n$ and $A_nA_1$ so that there are no two segments $A_iA_{i+1}$ and $A_jA_{j+1}$, with $1\leq ...
1
vote
0answers
96 views

Circumscribed simple line arrangements are 3-colourable?

An arrangement of $s$ lines are drawn in the euclidean plane so that no three lines intersect at a common point and no two lines are parallel. Now circumscribe this arrangement by a circle so that all ...
3
votes
0answers
19 views

Hypercube subdivision for a combinatorial problem

I have to design a combinatorial algorithm based on some simmetries of an hypercube and I'm pretty sure such a problem has already been studied. Let's start with a 3D case. Consider a cube like the ...
0
votes
0answers
9 views

lower bound for the length of the longest path contained in a subset of $\mathbb{Z}^d$

Let $A \subset \mathbb{Z}^d$ be a finte connected set. Let $\gamma$ be the longest self-avoiding path of nearest neighbors which is entirely contained in $A$. Can you provide a lower bound for the ...
0
votes
0answers
11 views

Minimal diameter of a connected subset of $\mathbb{Z}^d$

Let $A \subset \mathbb{Z}^d$ be a connected set of cardinality $|A|$. Let the diameter of the $A$ be defined as the length of the longest path of distinct, nearest neighbor sites which is entirely ...
1
vote
1answer
30 views

Height of $n$-simplex

$n$-simplex is a generalization of triangle or tetrahedron (with $n + 1$ vertices). The problem is to find its height. I kindly ask to check my solution. I am not fluent with $n$-dimensional space ...
9
votes
1answer
195 views

Obscuring squares of Rubik's cube

This is a combinatorial question related to Rubik's cube $3\times3\times3$ (and, in the end, its generalizations $n\times n\times n$). I assume that the readers are familiar with this puzzle. Let's ...
0
votes
1answer
28 views

Maximizing the volume of the convex hull of $N$ points in the unit ball

Suppose we are given an integer $N\ge4$, and we have to pick $N$ points in a unit ball in $\mathbb R^3$ to maximize the volume of their convex hull. Are those points necessarily on the surface of the ...
4
votes
2answers
112 views

Maximum distance between points in a triangle

An equilateral triangle has sides of unit length. a)Show that if five points lie in/on the triangle, then at least two of the points lie no farther than 0.5 units apart. b)Show that 0.5 cannot be ...
0
votes
0answers
26 views

Sufficient conditions to decompose a graph into pair-wise edge disjoint cycles?

Are there any conditions which will guarantee that for a graph $G$ of sive $v$, we could cut edges in such a way that what we're left with is a graph of $v/n$ disconnected components, where each ...
1
vote
0answers
35 views

A generalization of a geometry Olympiad problem involving $kn$ colored lines and a circle.

Let $n$ and $k$ be positive integers. Let $L$ be any set of $kn$ lines in the plane, no two of which are parallel. Each line in $L$ is colored one of $k$ colors, and there are $n$ lines of each color. ...
1
vote
1answer
40 views

Number of balls covering a $n$-dimensional sphere [closed]

What upper bounds for number of covering a unit sphere balls with a same radius $r$ and centers on this sphere are known?
3
votes
1answer
57 views

An upper bound on the sum of the lengths of chords

Problem: Several chords are drawn in a circle of radius $1$, and each diameter of the circle intersects no more than four of them. Prove that the sum of their lengths does not exceed 13. I couldn't ...
1
vote
1answer
42 views

Given two sets of points in the plane, there exists a point with equal sum of distances to the points in each set

Let ${A_1, ..., A_n}$ and ${B_1, ..., B_n}$ be two given sets of points in a plane with different centroids. Prove that there exists a point $P$ in the plane such that $\sum |PA_i| = \sum |PB_i|$. ...
4
votes
1answer
68 views

Combinatorially equivalent polyhedron with vertices from a given dense set

In this question we are only interested in convex polyhedra in the Euclidean space $\mathbb R^3$. Polyhedra $P$ and $P'$ are said to be combinatorially equivalent iff there is a bijection between ...
1
vote
1answer
29 views

Scalene rectangulation of a square: let me count the ways

A rectangulation of a square is a dissection of the square $S$ into smaller rectangles $R_i$, $i=1,\ldots,n$ with the usual caveats: $S = \cup_i R_i$ and the interiors of distinct rectangles ...
2
votes
0answers
41 views

A circle can include all but one of n points, but which one can it be?

The answers to the question "Circle enclosing all but one of n points" demonstrate that, given $n$ points, it is possible to construct a circle such that all but one of the points is inside the circle ...
19
votes
6answers
727 views

Circle enclosing all but one of $n$ points

It looks like a simple question but it turns out rather difficult to me. Here is the question: Given $n$ points on the plane, can we always draw a circle that includes exactly $n-1$ of them?
1
vote
0answers
24 views

On partitioning a finite set of points in the plane by drawing a line

Number of ways to separate $n$ points in the plane The linked answer was to this question: Suppose you have $n$ points in the plane, no two of which are colinear. How do you show that the number of ...
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, ...
0
votes
1answer
40 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
36 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
22 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 ...
6
votes
2answers
432 views

Positivity of the alternating sum associated to at most five subspaces

Let $V_1 , V_2 , \dots , V_n $ be vector 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
44 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
25 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
180 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
41 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) ...
4
votes
1answer
60 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
46 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
13 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
53 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
111 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
26 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 ...
2
votes
0answers
44 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
19 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 ...
10
votes
2answers
210 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
85 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?
4
votes
1answer
59 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 ...
1
vote
0answers
33 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 ...