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.

209 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
15
votes
1answer
254 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}?$$ ...
10
votes
0answers
253 views

$200n$ diagonals are drawn in a convex $n$-gon. Prove that one of them intersects at least $10000$ others.

$200n$ diagonals are drawn in a convex $n$-gon. Prove that one of them intersects at least $10000$ others. There was no information about $n$ in a original problem. Attempt: Choose at random and ...
10
votes
0answers
340 views

Maximum number of regions of a sphere partitioned by $\binom{n}{3}$ planes from $n$ points

We can place $n\in\mathbb{N}$ points on the surface of a sphere in a configuration so as to maximize the answer. A plane is defined by $3$ points. We create all $\binom{n}{3}$ planes from the $n$ ...
9
votes
0answers
1k views

Fractal Pattern from Queen's Move Construction

This question relates to the OEIS sequence A279212. Fill an array by antidiagonals upwards; in the top left cell enter $a(0)=1$; thereafter, in the $n$-th cell, enter the sum of the entries of ...
9
votes
0answers
360 views

Prove 2017 points in a plane cannot form 2017 triangles with the largest area

I haven’t got an idea about this problem . Could someone help me? Suppose 2017 points in a plane are given such that no three points are colinear. Among the triangles formed by any three of these ...
8
votes
0answers
199 views

Points at Integer Distances in 3-space

With the restriction no three points in a line, no four points on a circle, there is a 7 point configuration of points on the plane such that all pairs of points are at integer distances. 1 For 3-...
8
votes
0answers
413 views

Expected Number of Convex Layers and the expected size of a layer for different distributions

It is well-known that the expected number of vertices on the convex hull of random set of points in the plane distributed uniformly within a $k$-gon is $O(k\log n)$ and within a smooth shape (e.g. a ...
6
votes
0answers
72 views

Is this kind of “Gerrymandering” NP-complete?

Consider the following simplified form of "Gerrymandering": You have $n^2$ squares arranged as an $n\times n$ matrix. Each square is marked with either $0$ or $1$ which means a "voter preference" ...
6
votes
1answer
287 views

Upper Bound for Vertices of Intersection of Subspace and Simplex

Let $S$ be a simplex in $\mathbb R^m$. It can be expressed as the convex hull of the columns of some affinely independent $m \times m + 1$ matrix $A$: $$S=\left\{A\vec\alpha: \vec\alpha\in\mathbb R^{...
6
votes
1answer
412 views

Suggested name for “inflated” tetrahedron

What's the name or class of the following tetrahedron-like shape? Sketchup Model WebGL 3D-viewer It's apparently some sort of (not strictly convex) shell of a tetrahedron and it's scaled spherical ...
6
votes
0answers
382 views

dissection of rectangle into triangles of the same area

Given $m \times n$ rectangle with area $A$, and $m,n \in \mathbb{N}$. Let $S_k(m,n)$ be the number of way to dissect this rectangle into $k$ non-overlapping triangles whose area is $\frac{A}{k}$. It ...
5
votes
0answers
47 views

Prove that every point has been assigned the same number.

Question: Every point in a plane is assigned some real number. It is found that for any triangle, the number at its incenter is the arithmetic mean of numbers at the vertices. Prove that every ...
5
votes
4answers
264 views

Symmetric matrix as a sum of symmetric matrices

Let matrix $M \in \mathbb{N}^{5 \times 5}$ be symmetric with non-negative integer entries and zeros on the main diagonal and having the property that the row sums are equal to $2r$ for some $r \geq 2$....
5
votes
0answers
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 ...
5
votes
0answers
290 views

Geometric interpretation of k-th power of first n natural numbers and summation using Pick's theorem

I want to know is there any interesting properties of this approach or generalization to find $S_k(n)=1^k+2^k+3^k+\cdots+n^k$ by using Pick's Theorem $S=i+\tfrac{b}{2}-1$, where $i$-number of ...
5
votes
0answers
146 views

Minimum number of points chosen from an $N$ by $N$ grid to guarantee a rectangle?

What is the maximum number of points that can be chosen from an $N$ by $N$ grid such that no $4$ of the chosen points form a rectangle with sides parallel to the axes of the grid? Equivalently, what ...
5
votes
1answer
378 views

Generating M well separated points in an n-dimensional hypercube

I want to generate M n-dimensional points constrained inside a hypercube such that the points are relatively well separated. I'm playing around with this using a scripting language like R or python. ...
5
votes
1answer
223 views

How many cuts does it take to remove any $n$ vertices from an $m$-dimensional hypercube?

For instance, in $m=3$ dimensions (cube), the following $n=3$ corners (red) can be cut off with a minimum of $C=2$ planes (blue). (Note you are only allowed to cut off the vertices in red.) So what ...
5
votes
0answers
120 views

Linear Independence Game

Suppose you have a set $X$ of vectors in $\mathbb{F}_2^n$, with $|X| \ge n+1$, and consider the following game. On their turn, each player (2 player game) chooses from $X$ one vector and sets it aside ...
5
votes
0answers
171 views

Limits to the growth of the volume of a union of spheres

Assume that $x_i$, $i=1,\ldots,m$ are points in $\mathbb{R}^n$, with the maximal distance between any two of them being at most $1$. Define $$ a(r)=\mu\Bigl(\bigcup_{i=1}^m B(x_i,r)\Bigr),$$ where $\...
5
votes
0answers
205 views

Points and lines covering them

Let $n$ be a positive integer. A subset $S$ of points in plane satisfies the following conditions: a) We can't find $n$ lines in plane, such that every element of $S$ belongs to at least one of these ...
4
votes
0answers
75 views

Tiling a rectangle with both rational and irrational sided squares

We define a 'tiling of rectangle with squares' as the process of dividing the rectangle into finitely many squares so that they do not overlap and cover up the whole rectangle. Here is my question: ...
4
votes
0answers
85 views

When are there $n$ elements in $\mathbb{Z}_n^2$ with all differences distinct?

For which natural number $n$ are there elements $\{x_i\}_{i=1}^n \subset \mathbb{Z}_n^2$ such that $x_i - x_j = x_k - x_l$ if and only if $i = k$ and $j=l$ (i.e. such that all differences between the ...
4
votes
0answers
150 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 R^2$...
4
votes
0answers
49 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
0answers
55 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$. Intuitively,...
4
votes
0answers
169 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]
4
votes
1answer
55 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$ ...
4
votes
0answers
185 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 ...
4
votes
1answer
284 views

The Erdős-Szekeres problem on points in convex position

The Erdős-Szekeres problem on points in convex position and its proof using Ramsey theorem are well know. The problem goes like this: For every natural number $k$ there exists a number $n(k)$ such ...
4
votes
1answer
202 views

$K_{2^p+1}$ is not a union of $p$ bipartite graphs

What I want to show is that among $2^p+1$ points in the plane there are three that determine an angle of size at least $\pi(1-1/p)$. I was told I have to start with showing for $n=2^p$ that the graph ...
4
votes
0answers
56 views

Internal angle of a vertex of degree $d$ in $\mathbb{E}^2$ and $\mathbb{S}^2$

I am currently working on determining the maximum number of times the minimum spherical distance can occur among $n$ points in $\mathbb{S}^2$, and I have the following question. In $\mathbb{E}^2$, ...
3
votes
0answers
26 views

Trying to track down Sperner's lemma with signed counting of triangles

40 years or so ago, a kid named Jeremy showed me a proof of the two-dimensional Brouwer fixed-point theorem, which used what I have since come to know is called "Sperner's lemma." The two-...
3
votes
0answers
59 views

In an $n\times n$ grid with diagonals, how to count number of paths along the diagonals?

Given an $n\times n$ grid, with two diagonals in each unit square. I am interested in the number of (directed) paths or walks from one side of the grid to the opposite side, walking along the ...
3
votes
0answers
38 views

A game on a regular (2n+1)-agon

A and B play a game on a $(2n+1)$-agon where $n\ge 1, n\in\mathbb{N}$ They draw diagonals such that every diagonal drawn i) Cannot be previously drawn ii) only intersect an EVEN number of drawn ...
3
votes
0answers
66 views

Maximum number of umbrellas that can be added in a one kilometer beach?

Suppose we have a beach of length $1-$km. Suppose one Day $0$, the beach is empty. One day $1$, a family comes and puts their umbrella at some point in the beach. This point is fixed forever and ...
3
votes
0answers
41 views

Subsets of the circle not contained in a semi-circle

I'm reading a paper (Bullett and Sentenac, "Ordered orbits of the shift...", Ergodic Theory and Dynamical Systems), and have found that a proposition (Proposition 1) is (1) slightly incorrect (I have ...
3
votes
0answers
104 views

Relationship between Affine Dependence and Linear Dependence in Oriented Matroids?

I'm reading "Lectures on Polytopes" by Gunter Ziegler. The author first introduces the components of oriented matroids in affine case, then making a transition to linear case, with the condition "1z ...
3
votes
0answers
196 views

A Combinatorial Geometry Problem With A Solution Using Extremal Principle

I have solved this following Combinatorial Geometry Problem using extremal principle.Please check whether this solution is correct or not.Also write if you have any other solution. Problem :- Let $...
3
votes
3answers
753 views

Determining Neighbors in a Geometric Hexagon Pattern

Given a hexagonal grid enumerated from a center point (see example), how can one mathematically determine if two hexagons are adjacent to another? Edit: Asked another way, Given two non negative ...
3
votes
0answers
114 views

hypercube subdivision

Let $n$ be a positive natural number. For all $\emptyset \subset S \subseteq \{1, \ldots, n\}$ and $k \in \mathbb{Z}$, define the hyperplane $H(S,k)$ in $\mathbb{R}^n$ given by the equations $$H(S,k):=...
3
votes
0answers
87 views

Counting the partitions of a square into triangles

$\textbf{Problem:}$ The player has cut a square into $57$ triangles and painted a blue dot at all their vertices. It turned out that the blue dots are only inside the square (not on the sides) and in ...
3
votes
0answers
53 views

Linear bound on maximal rectangle in a permutation

Given $n$ coloured squares in an $n$ by $n$ square board of unit squares, one in each row and column (which we will call a permutation), let the minimum area (over all permutations) of the largest ...
3
votes
1answer
33 views

If every three segments from set have common interesecting line, than there exist line passing through all segments from this set

There are given lines segments in a plane such that for any three of them there exists a line intersecting them. Prove that there exists a line intersecting all these segments. Perhaps I should use ...
3
votes
0answers
95 views

Number of possible 'chains' made from $n$ rings

If we have $n$ rigid circles of the same radius we can form 'chains' on the plane by placing them in such a way that they intersect (here two circles intersect if and only if they have $2$ common ...
3
votes
1answer
160 views

How to prove the solution of these inequalities is empty?

Prove: There does not exist 4 unit vectors $\mathbf{v}_1$, $\mathbf{v}_2$, $\mathbf{v}_3$, $\mathbf{v}_4$ in $\mathbb{R}^3$ such that $$ \left \{ \ \begin{array}{ll} \dfrac{4}{3} < \left \|\...
3
votes
0answers
592 views

$\epsilon$- net theorems

Here we are going to consider problems of the following type: We have a family set F of satisfying certain conditions, meaning that we can choose a bounded number of points such that each set of F ...
3
votes
0answers
172 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 ...
3
votes
0answers
32 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
0answers
251 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
2 3 4 5