# Questions tagged [combinatorial-geometry]

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.

656 questions
Filter by
Sorted by
Tagged with
54 views

### Manufacturing desired planks from an existing pile of planks

Suppose there is a pile of commensurable planks that only may differ in lengths $0<a_1\leq\cdots\leq a_m$, which are to be used to manufacture planks of length: $0<b_1\leq\cdots\leq b_n$. ...
221 views

### How many components are required for partitioning a square between two colors?

Suppose $n$ disjoint points, some red and some blue, are organized on a line. We want to partition the line to two subsets, one containing all the red points and one containing all the blue points. ...
107 views

### How to cut a square on $5$ squares?

We can cut any square on $n$ squares if $n>5$ and $n=4$. The proof is easy by induction. Base cases $n=6,7,8$ are easy to find and then since we can cut a square on $4$ squares we get $3$ new ...
99 views

### Ratio between farthest and second farthest distance

$n\geq 3$ points lie in three-dimensional space. What is the largest $c(n)$ such that there always exists a point for which the ratio between the distance to the farthest point from it and the ...
52 views

### Partition of a regular polygon

Find the values of $n$ such that there exist a regular polygon with $n$ vertices such that can be partitioned with isosceles triangles with the vertices ...
140 views

### Simple disproof of Danzer — Grünbaum conjecture

A set of points in $\mathbb R^n$ is acute if any three points from this set form an acute triangle. In 1962 Danzer and Grünbaum conjectured that cardinality of acute set in $\mathbb R^d$ is $2d-1$, no ...
195 views

### Number of ways to distribute objects, some identical and others not, into identical groups

The question I initially thought of that prompted this was "How many distinct integer-sided cuboids are there with a volume of $60^3$?". A small example to clarify: There are $3$ integer-sided ...
95 views

### What is the least amount of pieces on a board with the following conditions:

There's an infinite board. Imagine you add a rectangle of $m*n$ pieces. With $m,n \geq 2$ (There's a piece every square, and you can't put one above other.) You can make a piece 'jump' other that is ...
53 views

### A is the set of all triangles whose perimeter is 2013. B is the set of all triangles whose perimeter is 2016. Which set has more triangles.

Let A be the set of all triangles whose lengths of sides are integers and whose perimeter is $2013$. Let B be the set of all triangles whose lengths of sides are integers and perimeter is $2016$. ...
30 views

### Acute set in three-dimensional space

I'm trying to prove the following statement: Prove that every set of more than $8$ points in the three-dimensional space determines at least one obtuse angle. I'm aware that the generalization of ...
211 views

### Design of a peculiar Wheel of Fortune

Consider the two wheels of fortune illustrated below. The first one (left) is constituted by $c$ sectors with the same arc length: $\alpha$ of which are red, $\beta$ of which are blue and $\gamma$ of ...
77 views

### Color the edges and diagonals of a regular polygon

Here is the problem: For what $n$ is it possible to color the edges and diagonals of an $n$-side regular polygon with $\dfrac{\binom{n}{2}}{3}$ colors, such that you use every color exactly three ...
338 views

### Looking for help developing an algorithm to solve a 2D rectangle packing/bin problem.

I need to develop an algorith to determine the optimum packing arrangement of dimensionally identical rectangles in a large rectangle of fixed size. 90 degree rotations are permitted. I've researched ...
57 views

### Does a circle give the largest smallest distance between two points that bisecting the perimeter

The title may seem a bit confusing, let's use math notation. Let $c:\mathbb{R}\to \mathbb{R}^2$ be a simple closed curve parametrized by length. A pair of points on the curve that bisect the ...
98 views

### Are (quasi-)regular polytopes uniquely determined by their edge graph?

I consider polytopes $P\subset\Bbb R^n,n\ge 2$ of arbitrary dimension (intersection of finitely many halfspaces, therefore convex), which are vertex- and edge-transitive (also called quasi-regular). ...
46 views

105 views

### Probability of hypercube vertices being within the unit n-hypersphere

Three uniformly distributed i.i.d points inside the unit n-ball centered at the origin are picked $p_1, p_2, p_3$ they are chosen such that $\|p_1\|>\|p_2\|,\|p_3\|$ , where $\|p\|$ is the ...
130 views

### Comparison of the numbers of colored squares in a checkerboard colored with red green and blue

The squares of a checkerboard $n \times n$ are colored alternatively in red, blue and green so that: next to a red square, there is a blue square; next to a blue square, there is a green square; next ...
320 views

### Splitting a shape into a number of congruent shapes similar to the original; analogues to A4 paper system

Two A4 papers can be put side by side to create a new rectangle that is similar to the original rectangles. Similarly, 5 right triangles with the length ratio between legs of 1:2 can be put to ...
59 views

### Can we paint the plane in two colors such that there is no square of the same color? [duplicate]

We have our every day plane $\mathbb{R}^2$ which we want to paint using two colors in such a way that no four points form a square of the same color. This means that for any square on the plane its ...
56 views

### What breaks down in the theory of affine hyperplane arrangments?

It appears to me that there is a substantial amount of combinatorial algebra and geometry supporting the theory of central hyperplane arrangements (See Topics in Hyperplane Arrangements, Aguiar and ...
38 views

31 views

### Circuit(cyle)-hyperplanes in a graph

Im currently working in matroid theory problem involving graphs. A circuit-hyperplane in a matroid is a circuit with |r| elements in a Flat of |r-1|. Translated into a graph the circuit-hyperplane ...
238 views

### Finding the dimensions of a Hypercube by the number of its edges

What is the dimension of a hypercube with 524,288 edges? I know that for $Q_n$, the number of edges is $(\frac{1}{2})n2^n = n2^{n-1}$. So I wrote this down in my book: (\frac{1}{2})n2^n = n2^{n-1}...
307 views

169 views

### How many right triangles can be constructed?

A right triangle $PQR$ is to be constructed in the $xy$-plane so that the right angle is at $P$ and line $PR$ is parallel to the $x$-axis. The $x$ and $y$ coordinates of $P$, $Q$ and $R$ are to be ...
2k views

### Number of paths in a grid below a diagonal [closed]

Given there is a $n\times n$ square grid . I was trying to calculate the number of paths from $(0,0)$ to $(n,n)$ under the condition that one might move either up or to the right one step at a time. ...
It is well-known that $n$ chords divide any convex shape into at most $\frac{n^2+n+2}2=T_n+1$ regions – the lazy caterer's sequence. For example, the pancake below is cut into seven pieces by three ...