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.

548 questions
25 views

How to divide a set of $n$ points of the plane into two subsets so that $MA_1+ MA_2+ …+MA_k= MB_1+ MB_2+ …+MB_{n-k}$ for some point $M$?

Definition. If a some set of $n$ points of the plane can be divided into two subsets $\{ A_1, \; A_2, \; ..., \; A_k\}$ and $\{ B_1, \; B_2, \; ..., \; B_{n-k}\}$ so that there is a point $M$ of the ...
54 views

Divide the chessboard

Suppose you have marked all the 64 centers of unitsquares of a chessboard. At least how many lines do you need, such that they divide the plane in a way, such that no two marked points lie in the ...
80 views

Partition of a rectangle into squares problem

recently I encountered this problem: "Show that a rectangle can be partitioned into finitely many squares if and only if the ratio of its sides is rational." I have found the a solution which I need ...
16 views

Permutations on a grid with repetition allowed

I understand how to calculate the number of permutations given a latin grid, but this problem is not that. Given a $4\times4$ grid, how many unique ways are there to arrange the numbers $1, 2, 3$ ...
28 views

Maximum number of nodes in a circle, with distance constraint

Given a circle $C$ with known radius $r$, I want to determine the maximum number of nodes in the circle, where there is a distance constraint between each two nodes equal to $s$, i.e. each two nodes ...
76 views

How many vertices can a hypercube-hyperplane intersection have?

Consider the n-hypercube $[-1, 1]^n$, and intersect it with an n-hyperplane. The intersection is in general an $(n-1)$-dimensional polytope. How many vertices can it have? For example, when $n=2$, it ...
34 views

Is packing rectangles exactly into a larger rectangle NP-complete?

I want to pack a number of rectangles into a larger rectangle, however, unlike other questions that I could find, I would like to do so exactly, without allowing any wastage. I do not really care ...
50 views

Create projective plane

Please explain this https://math.stackexchange.com/a/463369/672948 in a simpler way. I am not from higher mathematics background and these terms are quite hard to understand. I am clear upto finding ...
40 views

Graph factorisation

I have a graph having 6 vertices and its presentation is $E_{12}^4E_{13}^5E_{14}^6E_{24}^9E_{25}^2E_{35}^9E_{36}L_5^4L_6^{14}$. This means that there are $4$ edges connecting the vertices $1$ and $2$, ...
65 views

Understanding a step in an inductive proof that $n$ hyperplanes in $\mathbb{R}^d$ determine $\sum_{0\leq i\leq d}\binom{n}{i}$ cells ($d$-faces)

In the book Lecture Notes on Discrete Geometry by Jirka Matousek, in page 127, a theorem is proved: The number of cells ($d$-faces) in a simple arrangement of $n$ hyperplanes in $\mathbb{R}^d$ ...
153 views

29 views

Fewest number of distinct distances between $n$ points in $\mathbb Z^2$

I've been thinking about proving some bounds for the OEIS sequence A319476: $a(n)$ is the minimum number of distinct distances between $n$ non-attacking rooks on an $n \times n$ chessboard. I'd ...
37 views

Coloring the plane and the space with four and five colors

Here are two problems, each one is an olympiad combinatorics problem with coloring the plane and space. A) The plane is colored with four colors. Prove that it is possible to choose three different ...
129 views

Strange succession

An ant starts from the origin of a cartesian plane and makes $n \ge 2$ steps of lengh $d_1, d_2, \cdots, d_n$. Is there a condition (necessary and sufficient) on $d_i$'s for which the ant can come ...
107 views

Moscow Seven Sisters

Fix $n$ points in the plane in generic position, i.e. no three of them on the same line, etc. The number of lines joining two of them is ${n \choose 2}$. The number of regions in which $\ell$ lines ...
134 views

Stirling numbers and left right minima

How does one prove that the # of n- element permutations with k left-right minima is given by the 1st kind stirling number? I understand one should consider sigma(1)=n and sigma(1)=/=n, but I am ...
40 views

Moving Point in a set of non-concurrent lines

In a plane we have N lines, no two of which are parallel or perpendicular, and no three of which are concurrent. A cartesian system of coordinates is chosen for the plane with one of the lines as the ...
49 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$. ...
211 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. ...
83 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 ...
85 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 ...
49 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 ...
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 ...
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 ...