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.

Filter by
Sorted by
Tagged with
1 vote
1 answer
52 views

Trouble with counting the number of closed walks on a $n$-cube

I was trying to understand the second answer to the post Number of closed walks on an n-cube by @Ira Gessel. I understand the first part, that the closed walks of length $r$ on a n-cube can equals $2^...
user avatar
  • 2,405
-2 votes
0 answers
32 views

The smallest ineteger to enshure that there are n points whose center of gravity has inetger coordinates? [closed]

Let f(n) be the smallest positive integer that satisfies the Following : given f(n) points in the plane with integer coordinates ,there are n of them whose center of gravity has integer coordinates .
user avatar
3 votes
1 answer
77 views

Do $4$ balanced points on a sphere form a tetrahedron or lie on a plane?

Let $\mathbb{S}^2$ be the unit sphere in $\mathbb{R}^3$, and let $x_1,x_2,x_3,x_4 \in \mathbb{S}^2$. Suppose that $\sum_i x_i=0$, where we sum the vectors in $\mathbb{R}^3$. Question: Does one of the ...
user avatar
  • 23.1k
2 votes
0 answers
61 views

Explicitly describe the cryptomorphism between greedoids and greedy set operators

A greedoid $\mathcal{F}$ on a finite ground set $E$ is cryptomorphic to an operator $\sigma$ (usually - and improperly - called the closure operator of the greedoid) such that: $X \subseteq \sigma(X)$...
user avatar
  • 4,122
2 votes
0 answers
14 views

Book and study recommendations - discrete geomtry

I am a Computer Science graduate student and my research topic (if you can call it that, since I just started) is discrete geometry. Stuff like Helly's theorem, convex geometry, p-q theorems, epsilon-...
user avatar
  • 312
1 vote
0 answers
35 views

Find area with most points in a 2D plot

Assume I have got a set of points; their locations are scattered around a 2D plane. Like: p0 = x0, y0 p1 = x1, y1 p2 = x2, y2 ... pn = xn, yn We will be given a ...
user avatar
3 votes
2 answers
97 views

$4$ red cubes, and $4$ yellow cubes- create a $2\times 2\times 2$ cube

I have $4$ red cubes, and $4$ yellow cubes, all of dimension $1\times 1\times 1$. How many ways to create a new cube of dimension $2\times 2\times 2$, such that each new cube is distinct (i.e cannot ...
user avatar
  • 218
5 votes
0 answers
40 views

Find a $\mathbb{Z}_2$-invariant $S^4$ in the box complex of the partition graph $\mathcal{P}(3^3)$.

Every vertex of a partition graph $\mathcal{P}(g^g)$ is a partition of $\{1,2, ..., g^2 \}$ into $g$ cells of size $g$. Two vertices $u$ and $v$ are adjacent if the intersection of each cell of $u$ ...
user avatar
  • 195
0 votes
0 answers
34 views

Moving toward the destination on the plane with finite disjoint segments as obstacles, and bypass the obstacles greedily

There are $N$ disjoint segments and two points ($P_0$ and $O$) on the plane. Do the following operations to get $P_{i+1}$ with $P_i$, until $P_i=O$: Among the segments that intersects with $P_iO$, ...
user avatar
0 votes
2 answers
41 views

Prove that the number of $k$-simplexes in an $n$-orthoplex is $2^{k+1}\binom{n}{k+1}$ (where $n,k \in \mathbb{N}$ with $0 \leqslant k < n$)?

In the book 'Regular Polytopes' (H.S.M. Coxeter, 1973), Coxeter describes the $n$-orthoplex (which I will refer to from now on as $\beta_{n}$, and is the $n$-dimensional analogue of the octahedron) ...
user avatar
0 votes
0 answers
41 views

Combinatorial geometry: lines in general position, additional line intersects other regions

Let $\mathcal{L}$ a set of lines in general position (no three concurent lines, no two parallel lines) and let $\ell$ a line that crosses a number of regions (finite or infinite regions) determined by ...
user avatar
1 vote
1 answer
72 views

How many 3D shapes can be made from five cubes

How many different ways can five cubes be arranged such that at least one face is touching. For example, in the photo the top three show possible arrangements, but the bottom one is not allowed as the ...
user avatar
0 votes
0 answers
70 views

Counting intersections of hyperplanes

Consider two families of hyperplanes $F_1$ and $F_2$ in $\mathbb{R}^d$ both containing $n$ hyperplanes. We have that for all $f \in F_1$ and $g \in F_2$ that $f$ and $g$ intersect. Further we know ...
user avatar
  • 300
6 votes
3 answers
248 views

existence of $99$ lines in $\mathbb{R}^2$ passing through $100^2$ boxes

Problem 5 from "Bernoulli Trials Problems for 2017" link Prove or disprove the following: there exist $99$ lines in $\mathbb{R}^2$ so that for all $k,l \in \{1,2,\cdots, 100\}$, one of the ...
user avatar
4 votes
2 answers
90 views

On a condition of the Szemerédi–Trotter theorem

In the original paper from Szemerédi and Trotter: https://link.springer.com/article/10.1007/BF02579194 They state the theorem $1$ only if $\sqrt{n} \leq t \leq \binom{n}{2}$. Where $t$ is the number ...
user avatar
  • 300
2 votes
1 answer
53 views

Subsets which overlap in one element

consider the set $\{1,...,n\}$, we want to decompose it into sets $S_1,....,S_t$ such that $\vert S_i\vert \geq k$ for all i and $\vert S_i \cap S_j \vert \leq 1$ for all $i\neq j$. Is there an upper ...
user avatar
  • 300
2 votes
2 answers
63 views

What kind of non-optimisation packing problem is this?

You start with a big 2D shape (irregular polygon), and a set of smaller shapes. The goal is to figure out if the smaller shapes can fit within the big shape, without any overlaps. Rotations are ...
user avatar
4 votes
0 answers
94 views

Why are there finitely many of these approximations of $\sqrt{2}$? [duplicate]

I'm solving the following problem from a discrete geometry book (Lectures on Discrete Geometry, Jiri Matousek). Prove that for $\alpha=\sqrt{2}$ there are only finitely many pairs $m,n\in\mathbb{N}$ ...
user avatar
  • 309
1 vote
0 answers
34 views

Minimal distance between intersections of a regular grid parameterized by its change-of-basis matrix

Let a 2D grid basis $\mathcal{B}(\theta_1, \theta_2,r_1, r_2)$ whose change-of-basis matrix with respect to $\mathcal{B}_0$ the canonical basis of $\mathbb{R}^2$ writes : $$P_{\mathcal{B}_0}^{\mathcal{...
user avatar
1 vote
1 answer
66 views

Directed polyhedral graph with $d^+(v) \geq 1$ and $d^- (v) \geq 1$

Let $\Phi$ a convex polyhedron, with each edge being a vector (id est a directed line segment). For each vertex of the spatial object, let us define its $d^+(v)$ the number of vectors 'leaving' that ...
user avatar
4 votes
2 answers
72 views

Tucker's lemma, Borsuk-Ulam, triangulating a ball in *truly* antipodally symmetric fashion

I'm attempting to prove Tucker's Lemma from the Borsuk-Ulam theorem by means of the proof sketched as "immediate" on page 36 of Matoušek's Using the Borsuk-Ulam Theorem. In order to do this, ...
user avatar
1 vote
1 answer
48 views

What is a free element of a matroid?

I have often read the term free element of a given matroid $M$. However, I could not find a proper defintion of what a free element actually is. I know what the free matroid is but free elements seem ...
user avatar
  • 2,466
0 votes
0 answers
36 views

Maximum number of points with mutually distinct views of a set is $O(n^4)$

I'm looking at the following problem from Jiří Matoušek's Lectures on Discrete Geometry: Let $P = \{p_1, p_2,\dots p_n\}$ be a set of $n$ points in the plane. We say that points $x$, $y$ have the same ...
user avatar
  • 309
1 vote
1 answer
122 views

Problem while solving this combinatorial geometry puzzle

I'm a math olympiad trainee and received this problem during one of my practice tests. I have seen such problems before but always struggle to solve them. Any tips / solutions to this would be greatly ...
user avatar
5 votes
0 answers
140 views

Can identical rings intersect in any combinations in 3d space?

For every undirected graph G, with nodes $a_1,...,a_n$. Can we find n circles/rings of fixed radius, $c_1,...,c_n$ in 3 dimensions such that there exists an edge between $a_i$ and $a_j$ if and only if ...
user avatar
2 votes
1 answer
73 views

A collection of smooth manifolds with intersection property

This question is derived from a problem about conjugate points in Riemannian geometry. I have some doubt on the solution, so I'm proposing the most confusing part of it as a question. Let $M$ be a ...
user avatar
  • 1,517
1 vote
1 answer
228 views

Do you know the website of the journal Ars Combinatoria?

Do you know the website of the journal Ars Combinatoria? Is this journal still publishing articles? I have a paper accepted in 2018 by this journal, but now I cannot get any news and message from this ...
user avatar
  • 997
0 votes
0 answers
23 views

Covering $n$-simplex with $k$-subsets to produce a lower $m$-simplex, $m<n$?

Let vertices of an $n$-simplex be labeled $\{x_1,x_2,...,x_n\}$ and let the $k$-subsets or $k$-intersections ($k \leq n$)be identified as $x_{i_1} \cap x_{i_2} \cap ... x_{i_k}=x_{i_1}x_{i_2}...x_{i_k}...
user avatar
0 votes
0 answers
64 views

Combinatorial geometry: vectors in a regular hexagon with the square of the modulus of their sum that is a natural number, which is divisible by 4

We have a regular hexagon with sides of length $n \in \mathbb{N}^*$. On each side, we draw $(n - 1)$ points to split the side into $n$ segments of equal length - $\ell = 1$. We draw all the lines ...
user avatar
1 vote
0 answers
95 views

How many ways can n identical rings be interconnected (in 3 dimensions)?

I am thinking of two configurations of rings as being equivalent if you can physically move them from one configuration to the other without deforming the rings or have them intersect each-other. If ...
user avatar
1 vote
1 answer
58 views

Triangle game on $\mathbb{R}^2$: Can Alice always seek to construct equilateral triangles of length 1?

This is a game came to my mind last month. I have thought a lot and have searched the literature, only to find nothing much related. Alice and Bob are playing a triangle game on the Euclidean plane $\...
user avatar
2 votes
1 answer
55 views

Geometric realization of slice category

I'm studying the Appendix A to this paper, where they introduce the notions of geometric realization of an acyclic cetgory and polyhedral CW complexes. I did already study some algebraic topology, and ...
user avatar
  • 107
1 vote
0 answers
59 views

Prove there are at least $2$ lines with the property that each of them divides the plane into $2$ regions with the same number of red and blue points. [duplicate]

Let $n \geq 2$ a natural number, and $2n$ points chosen in plane, $n$ red points and $n$ blue points. There are no $3$ collinear points among the $2n$ points in plane. A 'good' line is a line that ...
user avatar
1 vote
1 answer
58 views

When is a polyhedron uniquely determined by its projections?

Let $P$ denote a polyhedron in $\mathbb{R}^D$ defined by the intersection of $k$ halfspaces, so $P = \{x\in\mathbb{R}^D : Ax\le b\}$ for $A\in\mathbb{R}^{k\times D}$, $b\in\mathbb{R}^k$. For a subset ...
user avatar
  • 2,945
1 vote
0 answers
20 views

A special Hyperplane Arrangement and a Ball

I have a hyperplane arrangement in $\mathbb{R}^d$ consisting of $d$ families of hyperplanes $F_1,...,F_d$ and a Ball $B$. I want to know in how many pieces the ball $B$ is cut at least. Furthermore I ...
user avatar
  • 300
0 votes
0 answers
31 views

Splitting $d+1$ pairs in $\mathbb{R}^d$ such that the two convex hulls intersect.

I am struggling with the following problem. Given $d+1$ pairs of points $P_i=(x_i, y_i)\in \mathbb{R}^d\times \mathbb{R}^d$, $i=0,\ldots ,d$. Show that we can split the pairs $P_i$ into $u_i$ and $v_i$...
user avatar
0 votes
0 answers
54 views

degenerate polyhedra as double polygons

Suppose with the term polyhedra we mean every collection of polygons that any two members can alwaysbe jointed together with a polygonal line passing from the interior of some of the edges of others. ...
user avatar
  • 3,122
3 votes
0 answers
162 views

$L$ is a finite set of lines in general position. Determine the number of discs inscribed in triangles enclosed by each triple of lines in $L$.

Let $\mathcal{L}$ be a finite collection of lines in the plane in general position (no two lines in $\mathcal{L}$ are parallel and no three are concurrent). Consider the open circular discs inscribed ...
user avatar
  • 86.2k
0 votes
1 answer
18 views

Existence of inscribed polygon in positive measure sets

Fix a convex $n$-gon $\Gamma$, is it true that for any subset $E$ of $\mathbb{R}^2$ with positive Lebesgue measure, there exist $n$ points in $E$, such that the associated $n$-gon of these points is ...
user avatar
0 votes
1 answer
54 views

What is a selection protocol for choosing from n teams so all teams play k other teams?

Note: this problem is similar to this previous question but this aspect of the query was not fully addressed there. First, if $n$ is even, $k$ can be any value from 1 to $n-1$. If $n$ is odd, then $k$ ...
user avatar
  • 121
1 vote
0 answers
39 views

How do I interpret the tropicalized curves (one of degree $6$ and one of degree $8$)?

For me, the topic of tropicalization is new and I am trying to understand what new insights and perspectives tropicalization could provide me on the following two curves (degree 6 and 8). So it is a ...
user avatar
5 votes
2 answers
215 views

Find number of arrangements of a cube if sum of numbers on each face must be same

Each vertex of a cube is to be labelled with an integer 1 through 8, without repetition, such that sum of numbers of the four vertices of a face is the same for each face. Arrangements that can be ...
user avatar
  • 717
3 votes
0 answers
70 views

What are the basic next steps to tropicalize a curve of degree $6$ (ideally using any CAS)?

First of all, I must admit that the topic of Tropicalization is new to me. I have a rough outline and I'm by no means asking for a ready-made solution here, but rather some pointers on how to get an ...
user avatar
24 votes
1 answer
245 views

Does a random set of points in the plane contain a large empty convex polygon?

Suppose I choose $n$ points uniformly at random from the unit square $[0,1]\times [0,1]$, obtaining a set of points $S=\{p_1,\ldots, p_n\}\subset [0,1]\times [0,1]$. Then $S$ may contain subsets which ...
user avatar
0 votes
0 answers
23 views

Interior of a closed polyline

I try to find some book or article with a discussion of the following question. The closed polyline divides the plane into some regions. Is it always possible to color them into two colors that any ...
user avatar
  • 968
1 vote
0 answers
18 views

Reference for Monochromatic Triangles version of the Hadwiger–Nelson problem

The following problem related to the Hadwiger–Nelson problem was proposed by Ron Graham in R. L. Graham. Open problems in Euclidean Ramsey theory. Geocombinatorics, XIII(4):165–177, April 2004. ...
user avatar
3 votes
2 answers
66 views

Sawtooth-like polygonal chains in $\mathbb R^2$ must self-intersect.

We consider closed polygonal chains in the 2-dimensional plane with an even number of sides, say $2n$, numbered as $A_1B_1A_2B_2\dots A_nB_nE$, where $E = A_1$. We require additionally, that each $B_i$...
user avatar
18 votes
1 answer
317 views

Combinatorial Geometric proof of $\binom{\binom{n}{2}}{3} > \binom{\binom{n}{3}}{2}$

Consider the following diagram for n=5: $\displaystyle \binom{\binom{n}{2}}{3}$ represents the number of ways to choose 3 rotationally distinct faces from the three sides of the entire diagonal ...
user avatar
2 votes
1 answer
43 views

Hyperplanes intersecting Ball

I'am considering an arrangement $\mathcal{H}$ of $n$ hyperplanes in $\mathbb{R}^d$ and a ball $B \subset \mathbb{R}^d$ such that every hyperplane intersects the ball non-trivially. I want to know into ...
user avatar
  • 300
2 votes
0 answers
21 views

Dual version of a generalization of Erdös-Beck theorem

in the Paper of Do he states that his theorem 1.6 also holds if one embeds $\mathbb{R}^d$ into $\mathbb{R}\mathbb{P}^d$, the theorem is: For any $0 < \beta < 1$ there is some constand $c(\beta)$ ...
user avatar
  • 300

1
2 3 4 5
17