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.
864
questions
3
votes
0
answers
37
views
What tools can show that (possibly irregular) dodecahedra do not fill space?
Here is a fairly natural question: Can three-dimensional space be filled with convex polyhedra of the same incidence structure (if not the same geometry) as the regular dodecahedron, such that four ...
- 15.7k
3
votes
2
answers
127
views
A line perpendicular to a tangent curved at both ends
I made a guess two years ago. I have a strong feeling that there is a proof using the fixed point theorem with geometric visualization, but I couldn't do the proof.
If you have a simple closed convex ...
- 752
2
votes
1
answer
223
views
Number of perpendicular diagonals in any regular polygon
Find the least positive integer n such that there are at least $1000$ unordered pairs of diagonals in a regular polygon with n vertices that intersect at a right angle in the interior of the polygon.
...
- 65
5
votes
0
answers
177
views
Counting problem about polygon triangulations
I have the following question about triangulations (by non-intersecting diagonals, and edges) of regular polygons.
What is the number of triangulations of a regular n-gon, up to all symmetry (i.e. the ...
- 560
1
vote
0
answers
17
views
Graph Distance of the Vertices of a Hypercube is Exponentially Bounded
Fix hypercube $\{ 0, 1 \}^n$. Let $A \subseteq \{ 0, 1 \}^n$ of size $|A| \geq 2^{n - 1}$. Then it is claimed $\forall t > 0$,
$$
|\{ \nu \in \{ 0, 1 \}^n: \mathrm{dist}_{\{ 0, 1 \}^n}(\nu, A) > ...
- 509
2
votes
1
answer
23
views
Number of Different Inscribed Triangles in a Circle with a Given Number of Equidistante Points on It
Is there a formula for calculating the number of different inscribed triangles in a circle with a given number of equidistante points on it? By "different" I mean that a triangle can't be ...
0
votes
1
answer
21
views
Package to enumerate all regular triangulations for point configuration
I am trying to enumerate the regular triangulation of some point configurations. The sage-math can enumerate all triangulations, but cannot check if each one is regular or not.
It seems TOPCOM can ...
- 137
1
vote
0
answers
29
views
Projecting sets onto lines or planes
I'm having some trouble picturing what some sets (such as lines/planes or arbitrary sets) look like when projected onto a line or a plane.
The particular example I have at hand is from a paper of Imre ...
- 322
0
votes
0
answers
12
views
Triples of Arrangements, An Introduction to Hyperplane Arrangements
I'm making my way through Richard P. Stanley's An Introduction to Hyperplane Arrangements, and am having a bit of difficulty processing the definition of triple's of arrangements. The document states, ...
- 141
1
vote
0
answers
19
views
Hyperplane arrangements - numbering regions by "regional distance" from a line
Consider the following statement (contrived to highlight an unknown piece of terminology):
For any $n$-dimensional space $\mathbb{R}^n$, a finite number of
$(n-1)$-dimensional hyperplanes in a ...
- 141
0
votes
0
answers
35
views
$k$-dimensional faces of an $n$-dimensional cube
I want to find a formula that shows the number of $k$-dimensional faces of an $n$-dimensional cube. By internet I found that this formula has a generating function, $(x+2)^n$, where the formula is the ...
- 427
1
vote
1
answer
137
views
Problem on geometric arrangement of lines in space
Consider a set of $n$ lines in $\mathbb{R}^3$ all concurrent in a point (let's call it center). Is it always possible to place a finite number of isometric copies of this set of lines in $\mathbb{R}^...
- 1,385
0
votes
0
answers
27
views
Which simplicial complexes are completely determined by the 1-skeleton of their dual cell complexes?
Consider the following line of reasoning that shows certain simplicial complexes (of arbitrary dimension) are completely determined by corresponding graphs:
The facet complex of any simplicial ...
- 1,260
1
vote
1
answer
83
views
Determine the minimum and maximum number of paths on a $2N\times 2N$ board
Here a path refers to a series of connected segments.
I have tried out small cases and have conjectured that the minimum is $4N$ and the maximum is $2N^2+2N+1$.
Construction for minimum:
Construction ...
- 2,638
0
votes
0
answers
28
views
Generalised Hadwiger conjecture for any n-dimensional body
I'm speaking in reference to Hadwiger's conjecture in combinatorial geometry "Can every $n$-dimensional convex body be covered by $2^{n}$ smaller copies of itself?"
Image from the wikipedia ...
- 13
3
votes
1
answer
98
views
Can you fit nine points, whose pairwise distances apart are all greater than 1, in an equilateral triangle with side length 3?
Can you show how to fit nine points, whose pairwise distances apart are all greater than 1, in an equilateral triangle with side length 3 or can you prove that it isn't possible to do so?
It is a ...
- 3,194
3
votes
1
answer
155
views
Book recommendations: Olympiad Geometry
As a 10th grader who'll take the ICSE exam in Q1 2024, I am planning to attempt the Indian Olympiad Qualifier in Mathematics next year, and quite hopefully RMO, INMO, and IMO afterward. I have found ...
- 41
1
vote
0
answers
33
views
Do perfect squared rectangles with corners of sizes 10, 12 and 13 exist?
A squared rectangle is a rectangle dissected into squares.
squared rectangles are called perfect if the squares in the tiling are all of different sizes and are positive integers.
The smallest perfect ...
0
votes
0
answers
9
views
Local h-polynomial with V=3.
I'm trying to understand an example that Stanley gives in his article "Subdivisions and local h vectors". It is example 2.3 part d).
If #V=3 and $h(\Gamma,x)=h_0+h_1x+h_2x^2+h_3x^3$ (so $...
- 1
0
votes
0
answers
50
views
Explanation of Linear Separability on a 3D Cube
The question of how many linearly separable boolean functions exist on an $n$-dimensional hypercube is a long standing problem without a solution. However, I am looking for an explanation of why the ...
- 1,047
4
votes
1
answer
78
views
A direction that is far from any n directions of the vertices of a hypercube
$C_n \stackrel{\text{def}}{=} \left\{\pm \frac{1}{\sqrt{n}} \right\}^n$
Question:
Is the following true?
For all $K>0$, $n$ large enough and $r_1,..,r_n \in C_n$, there exists a unit vector $c \in \...
- 531
2
votes
1
answer
42
views
Any face of a polytope is an intersection of the defining half-spaces
Let $P$ be a polytope in $\mathbb{R}^d$ given as the solution set to a system of linear inequalities $a_ix \le c_i$ for some row vectors $a_i$ and scalars $c_i$, $i = 1,\dots,n$. For each $i$ define $...
1
vote
1
answer
71
views
Polytopes: affine isomorphism implies combinatorial isomorphism
Let $P \subseteq \mathbb{R}^d$ and $Q \subseteq \mathbb{R}^e$ be (convex) polytopes. Define them to be affinely isomorphic if there is an affine map $f \colon \mathbb{R}^d \to \mathbb{R}^e$ whose ...
0
votes
0
answers
68
views
How to minimize this set function?
I'm considering a very interesting problem. For a graph $G=(V,E)$, either directed or undirected, if we define
\begin{equation}
\rho(G)=\max\{|\lambda|\;|\;\lambda\text{ eigenvalue of $G$'s adjacency ...
- 41
1
vote
0
answers
81
views
Covering a rectangle using squares
Given a set of Squares $\mathcal{S}=\{w_1, w_2, \ldots, w_n\}$ and a rectangle $\mathcal{R}$ of dimensions $a\times b$.
Is there a placement of the squares in $\mathcal{S}$ to cover $\mathcal{R}$.
The ...
- 111
1
vote
1
answer
57
views
Binary optimization on a direct-acyclic-graph(DAG)
Given a DAG $G$, each edge of the DAG $e \in E(G)$ relates to a attribute $w_e \in \{-1, 1\}$
Try to find the optimized attribute setting $[w_e]$ s.t. the cost function
$$
\sum_{e\in E(G)} w_e
$$
is ...
- 11
0
votes
0
answers
27
views
About the number of faces of the conification of a polytope
Let $P\subset\mathbb{R}^n$ be a polytope of dimension $(n-1)$ such that the origin $\vec{0}\not\in\text{Aff}(P)$, where $\text{Aff}(P)$ denotes the affine hull of $P$ in $\mathbb{R}^n$. Now, we ...
- 363
0
votes
1
answer
64
views
number of subrectangles
I have a square matrix generated by a cyclic shift of a vector which contains only 0's and 1's. For example,
$$
\begin{matrix}
1 \; 1 \; 0 \; 1 \; 1 \\
1 \; 1 \; 1 \; 0 \; 1 \\
1 \; 1 \; 1 \; 1 \; 0 \\...
- 113
4
votes
1
answer
148
views
In what sense is the sphere the limit of convex polyhedra?
It seems intuitively clear that the sphere can be approximated (both in surface area, but also in a more geometric sense) by certain classes of polyhedra. Do there exist any good formalizations of ...
- 167
0
votes
1
answer
67
views
Determine if you are inside or outside a closed region
You wake up in a desert and you find yourself next to a very, very long wall. All you know is that the wall forms a closed region. You are only allowed to walk in the space, and to put "flags&...
- 2,408
0
votes
2
answers
142
views
Number of rectangles generated by $n$ points in the plane
This sounds like a problem that would have been definitely studied by some paper, and to defend myself I have searched using various tools for some time to no avail.
What is the configuration of $n$ ...
user1010760
0
votes
0
answers
13
views
If two combinatorial polytopes have a subset of their cocircuits in common, will they have a triangulation in common?
In "Triangulations" by Loera, Rambau, and Santos, there is a Corollary (4.1.44) that states that two combinatorially equivalent (having the same oriented matroid) point configurations have ...
- 1
0
votes
0
answers
65
views
Maximum area of a lattice triangle with 1 interior lattice point
The original problem I had was constructing a conjecture about the number of boundary points on a lattice triangle with 1 interior lattice point. Using Pick's theorem, I have simplified this problem ...
- 100
1
vote
0
answers
70
views
Understanding the proof of Van der Waerden's theorem by Graham and Rothschild.
I am studying the proof of Van der Waerden's theorem by Graham and Rothschild. I have tried to understand each step, but I need to fill in some gaps. Van der Waerden's theorem says that:
$\forall k, r ...
- 11
6
votes
0
answers
63
views
Moving points into the black cells of an infinite chessboard [duplicate]
Given an infinite chessboard and $6$ points on it, you can rotate or translate the six points at the same time. How many points can you guarantee to move into (include boundaries) a black cell?
I ...
user1034536
1
vote
1
answer
59
views
Are there any points on the parameter plane that do not belong to any wake?
p/q-wake is the region of parameter plane enclosed by two external rays landing on the same root point on the boundary of Mandelbrot set main cardioid (period 1 hyperbolic component).
Are there any ...
- 1,706
3
votes
0
answers
85
views
Valid over/under assignments in a pile of sticks
Let's say we have an overhead view of a pile of $N$ (straight) sticks of nonzero thickness,
like so. Assume that each of the $I$ intersections involves just two sticks.
Now the picture as given has no ...
- 31
1
vote
2
answers
69
views
Show that the incircle is the largest circle which fits inside regular polygon
Consider a regular polygon with $n \ge 3$ sides. The incircle of the regular polygon passes through the midpoint of each sides and is also tangent to the sides at the midpoints. Intuitively, the ...
- 8,005
2
votes
1
answer
31
views
Maximum number of right interior angles in an $n$-gon
What is the maximum number of right interior angles in an $n$-gon for $n\ge 3$?
A naive approach based on summing the interior angles gives an upper bound of $\lceil 2(n+2)/3\rceil-1$; however I doubt ...
- 99
0
votes
2
answers
134
views
Square Tetris: covering a $4 \times 4$ square with (any) tetrominoes - Why no solutions with exactly $1$ $T$-piece?
(Given a certain application of this problem, I'm surprised I couldn't find any discussion about it specifically. I'm probably just searching for the wrong terms. In any case, this one's been ...
- 113
4
votes
0
answers
128
views
Line segments in the plane where each triple can be intersected by a common line
I have the following problem at hand:
We have a collection $\mathcal{C} = \{l_1,\dots, l_n\}$ of $n$ line segments in the plane where each segment is contained in a line through the origin. Assuming ...
- 63
2
votes
1
answer
49
views
What is the dimensionality of Euclidean space where $N$-star can be embedded?
How many dimensions are required to embed a star graph with $N$ vertices such that the following holds:
The embedding has unit radius i.e. $\| x_0 - x_i \| = 1$ where $x_0$ is the central vertex, $i \...
- 123
1
vote
2
answers
70
views
Making triangles with no common side from a polygon.
How many triangles can be formed by joining vertices of polygon such
that no two triangles share a common side?
I tried small cases
$n=3,4: 1 ; n=5,6: 2$
I first tried to calculate number of ...
- 129
3
votes
1
answer
62
views
Maximum number of concave quadrilaterals in n points in regular position
Consider N points in a plane. What is the maximum number of quadrilaterals that are concave? The minimum is always zero: form a convex polygon with all N points, and no 4 of the N will form a concave ...
- 103
12
votes
0
answers
382
views
Prove that the VC Dimension of Rotatable Squares in a Plane is $5$.
Pre-S: There is a counter example of 6 points! this problem is solved!
Prove that the VC dimension of rotatable squares in a plane is $5$.
Also, please look at the alternate statement below if not ...
- 2,539
2
votes
0
answers
25
views
Version of Helly theorem in the plane
This is a question from the book lectures on Discrete Geometry:
Let $C_1, \dots, C_n$ be convex sets in the plane such that each 4-tuple of them contains a ray in the intersection. Prove that $\...
- 423
0
votes
1
answer
28
views
K-Locality of Hilbert curve
Let $H: [0,1] \to [0,1]\times[0,1]$
be the Hilbert curve (the limit of the family of functions defined on this page )
This curve is well known for its "good locality propreties"
Meaning that ...
- 215
3
votes
1
answer
65
views
Combinatorial decomposition of summands in product
Let
$$
X=\{(i_1,\ldots,i_{n-1}) : i_j\in[1,n]\}.
$$
Is there a "natural" way to decompose $X=\bigcup_kX_k$ such that for $x\in X_k$, no coordinate of $x$ is equal to $k$?
For example:
[$n=2$...
- 9,559
2
votes
1
answer
118
views
Vertex minors of paths
(Vertex Minor) A graph H is a vertex minor of G if H can be obtained from G by a sequence of vertex deletions and local complementation
(Local complementation) A local complementation $\tau_v$ is a ...
- 300
3
votes
1
answer
35
views
Pinning evenly fragmented papers
Draw traces along two identical papers arbitrarily so that each one is divided into $k$ parts of the same size. Place $k$ pins through them with their boundaries coincided. Show that there exists a ...
user1034536