# Questions tagged [discrete-geometry]

Finite or discrete collections of geometric objects. Packings, tilings, polyhedra, polytopes, intersection, arrangements, rigidity.

1,559
questions

2
votes

0
answers

23
views

### Endpoints of intrinsic diameter of a convex polyhedron

Let $P$ be a convex polyhedron in $\mathbb{R}^3$, and $d(P)$ its intrinsic diameter,
i.e., the longest shortest surface path between two points. Say that $P$ is of
class
$D_0$ if neither endpoint of $...

3
votes

0
answers

57
views

### Counting homologically non-trivial and trivial cycles in $n \times n$ square lattice torus of a given length $l \geq n$

This should be a fairly standard question but I can't really seem to find a reference.
Consider an $n \times n$ square lattice torus $\mathbb T$. Given a length $l \geq n$, what is the number of ...

11
votes

1
answer

264
views

### Complexity of counting regions in hyperplane arrangements

Let $H_1,\ldots,H_n$ be hyperplanes in $\Bbb R^d$. Denote $\mathcal{H} :=\{H_1,\ldots,H_n\}$ and let $c(\mathcal{H})$ be the number of regions in the complement: $\Bbb R^d\setminus \bigcup H_i$.
...

5
votes

1
answer

91
views

### Partitioning convex polygons into triangles of equal area and perimeter

This post is based on https://math.stackexchange.com/questions/2822589/dissect-square-into-triangles-of-same-perimeter and On a possible variant of Monsky's theorem
Question 1: Is this statement ...

1
vote

0
answers

28
views

### What are some other methods for partitioning an n-dimensional space based on a set of points in that space?

So this is a very general question, but I'm curious if there are any other methods for partitioning an n-dimensional space based on the location of a set of points, either randomly chosen or specified,...

-1
votes

0
answers

76
views

+50

### Understanding a constant $c>0$ in a problem on mutually avoiding sets of points and lines

I came across the following problem that seems very interesting: if we have four mutually avoiding sets of total of $n$ points (that are in general position), say $\{A_1,A_2,A_3,A_4\}$ (i.e. sets in ...

1
vote

0
answers

44
views

### Diameter of a Cartesian product of two graphs [migrated]

If I am looking at a Cartesian product of two graphs $G_1$ and $G_2$ (defined here https://en.wikipedia.org/wiki/Cartesian_product_of_graphs).
I am trying to bound the diameter of the graph $G_1 \...

14
votes

7
answers

2k
views

### Finite set of non-collinear points on plane with every point having ≥ 3 equidistant neighbors? [closed]

Does there exist a finite set of points on the Euclidean plane, such that:
No 3 points are collinear, and
Every one of the points has (at least) three other points in the set at the same distance ...

0
votes

0
answers

33
views

### When can a compact metric space be covered by finitely many nearly-disjoint closed and convex sets?

This question is a follow-up of the following negative question.
Let $(X,d)$ be a (non-empty) compact metric space.
More generally than in the first post, I'll call a set of non-empty subsets $C_1,\...

2
votes

1
answer

49
views

### Determining if a polygon is convex using relations on orientation of each ordered triple of points

I am reading a paper by Szekeres and Peters on computing the 17-point case of the Erdős–Szekeres conjecture. The conjecture states that the minimum number of points in the plane (in general position, ...

7
votes

2
answers

192
views

### Are polyhedra with equilateral triangular faces rigid?

Convex polyhedra are rigid by Cauchy’s theorem. Steffen’s polyhedron is an example of a non-convex polyhedron that is flexible (i.e., non-rigid). However, it appears to have edges of different lengths....

3
votes

0
answers

123
views

### minimal set of words of length n

Given an alphabet $S={a_1,\cdots,a_m}$, we consider the words of length $n$, $S^n$.
We call two words $b_1b_2\cdots b_n$ and $c_1c_2\cdots c_n$ are connected if $b_i=c_i$ for some $i$.
We consider $P\...

26
votes

1
answer

2k
views

### Polyomino that can tile itself

Find all polyomino $P$ such that we can tile $nP$ with $n^2$ copies of $P$ for all $n\in \mathbb{N}$. ($nP$ is a polynomino similar to $P$ with scale factor $n$)
I conjecture that there are only $4$ ...

2
votes

1
answer

134
views

### Pairwise intersecting circles in the plane

If I am looking at a collection $\mathcal{C}$ of circles $\{C_1,...,C_n\}$ all of which have some radii $\{r_1,...,r_n\}$ where $r_i\in\mathbb{R}^{+}$ for each $i \in[n]$. In $\mathcal{C}$, all the ...

4
votes

1
answer

107
views

### On polyhedrons with specified numbers of congruent faces

Basic question: Given 3 integers n, n1 and n2 such that n1+n2 = n, to form an n-face polyhedron such that n1 of its faces are mutually congruent and the remaining n2 faces are different but congruent ...

1
vote

1
answer

49
views

### Representation of $x$-non-monotone curves with one intersection each by $x$-monotone curves

Take the $y$-axis and a set of $n$ curves starting from $y$-axis, labelled as $\mathcal{C}:=\{C_1,C_2,...,C_n\}$. These curves fulfill the following conditions:
The curves all have a starting point ...

2
votes

0
answers

52
views

### Tiling with triangles with same Steiner ellipses

We continue from Tiling with triangles of same circumradius and inradius .
Definitions: Given any triangle, its Steiner circumellipse is the unique circumellipse (ellipse that touches the triangle at ...

3
votes

1
answer

72
views

### Convex polygon shadows: Shortest equivalent segments

Let $P$ be a convex polygon.
Q1. What is the shortest collection of line segments $S$ inside $P$
with the property that both $P$ and $S$ have the same sequence of orthogonal shadows
as $P$ and $S$ ...

41
votes

1
answer

2k
views

### Does any set of dominoes tile some common figure?

Let $D_1,\dots,D_n \subset \mathbb{Z}^2$ be two-point sets, i.e. 'dominoes' (unlike common dominoes, these are not necessarily connected, but I couldn't come up with a better name).
Does there always ...

16
votes

1
answer

814
views

### Kakeya crossed-needles problem

The Kakeya needle problem asks for the
minimum area planar region in which one can completely turn around a line segment through
a series of translations and rotations. There is no minimum: There are &...

2
votes

0
answers

270
views

### Combinatorics of iterated composition of noncrossing partition polynomials

A combinatorial problem arises in relating connected and disconnected Green functions associated to a "zero-dimensional" quantum field theory presented by Brezin, Itzykson, Parisi, and Zuber ...

23
votes

1
answer

557
views

### Given a group action on a simplex, can I always find a fundamental region that is a simplex?

Let $\Delta\subset\Bbb R^n$ be a simplex with $n+1$ vertices. Let $G\subset\mathrm{GL}(\Bbb R^n)$ be a finite group of linear symmetries of $\Delta$, i.e. linear transformations that fix the simplex ...

1
vote

1
answer

78
views

### Triangles that can be cut into mutually congruent and non-convex polygons

It is easy to note that an equilateral triangle can be cut into 3 mutually congruent and non-convex polygons (replace the 3 lines meeting at centroid and separating out the 3 congruent quadrilaterals ...

2
votes

1
answer

248
views

### Maximal distance of set to integers

Let $x_1,...,x_N$ be $N$ mutually distinct real numbers.
I wonder: How does the expression
$$ f_x(N)=\sup_{\lambda \in \mathbb R}\min_{i \neq j} \min_{n \in \mathbb Z}\left\vert \lambda (x_i-x_j)-n\...

3
votes

0
answers

116
views

### Permutahedra Euler characteristic polynomials from cumulant-moment relation, a combinatorial proof?

Given the formal Taylor series, or e.g.f.,
$f(x) = 1 + \sum_{n \geq 1} m_n \; \frac{x^n}{n!}$,
the classical formal cumulants $c_n$ are generated from the formal moments $m_n$ via
$ \sum_{n \geq 1} ...

1
vote

0
answers

36
views

### Tiling with a one-parameter family of non-congruent triangles

This post continues Tiling with triangles of same circumradius and inradius.
The following are known about infinite sets of triangles that can be parametrized with one variable:
from an infinite set ...

4
votes

1
answer

92
views

### Given a polytope $P$ with bipartite edge-graph, if the bipartition classes are equal in size and lie on spheres, is $P$ inscribed?

Suppose that $P\subset\Bbb R^n, n\ge 3$ is a (full-dimensional) convex polytope with a bipartite edge-graph $G=(V_1\cup V_2,E)$ (for example, a zonotope). Suppose further that there are concentric ...

5
votes

0
answers

150
views

### Tiling with triangles of same circumradius and inradius

Consider a pair of positive real numbers $r$ and $R$ with $r<R/2$. Then we can form infinitely many triangles all with circumradius $R$ and inradius $r$.
For any such pair, the resulting triangles ...

3
votes

0
answers

45
views

### Simplex cover of an n-cube with non-congruent simplexes

I am curious about simplex coverings of the unit n-dimensional hypercube (or n-cube) with the following properties:
The simplexes do not need to be regular
The simplexes can be non-congruent (i.e. of ...

4
votes

1
answer

192
views

### Do combinatorially equivalent polytopes have the same triangulations?

A triangulation of a convex polytope $P\subset\Bbb R^n$ is a partition of $P$ into $n$-simplices $\{\Delta_1,...,\Delta_m\}$ each of which has all its vertices among the vertices of $P$. A polytope ...

1
vote

2
answers

85
views

### Name for the weight function defined as the integer sum of coordinate entries from ${\mathbf F}_p$

In ${\mathbb F}_p^n$, $p$ prime one may define a weight function on vectors in various ways such as Hamming, or Lee weight. (These two weights correspond nicely to the respective distances from $\bar ...

1
vote

0
answers

48
views

### Convex polyhedron in lattice points

Given $P$ a convex polyhedron with vertices in lattice points with $n$ faces.
a) what is the minimum volume of $P$.
b) what is the minimum area surface of $P$.
Paper: The minimum area of convex ...

8
votes

0
answers

96
views

### Is every simplicial $d$-sphere linearly embeddable in $\Bbb R^{d+1}$?

A simplicial $d$-sphere is a simplicial complex homeomorphic to the $d$-sphere. It is known that not every such complex can be embedded into $\Bbb R^{d+1}$ as the boundary complex of a convex ...

0
votes

0
answers

18
views

### History and bounds on hinged-ruler-packing problem?

A hinged-ruler of $n$ segments is a sequence $(a_1,a_2,\cdots,a_n)$ of reals from the interval $[0,1]$. The ruler takes the appearance of $n$ line segments joined at their endpoints with hinges, where ...

5
votes

1
answer

239
views

### Contracting a set to a ball

$\newcommand\R{\mathbb R}\newcommand\S{\mathbb S}$
Question 1: Let $S$ be a nonempty measurable subset of $\R^n$. Let $B$ be a closed ball in $\R^n$ such that $m(B)=m(S)$, where $m$ is the Lebesgue ...

8
votes

2
answers

263
views

### Symmetries of contractable subsets of $\Bbb R^n$

Let $K\subset\Bbb R^n$ be a non-empty compact subset of $\Bbb R^n$. A symmetry of $K$ is an isometry of $\Bbb R^n$ that fixes $K$ set-wise. Since $K$ is compact, there is always a point $x\in\Bbb R^n$ ...

5
votes

0
answers

54
views

### Roundest polyhedra: how well can we bound the edge count of their faces?

By "roundest" I mean having the lowest surface area for the highest volume, given a fixed number of faces $n$. There've been a few questions about them on here (including from me), but I'm ...

2
votes

1
answer

132
views

### On rigid packings of the plane with a constraint

This post continues Thinnest rigid packings of the plane
A packing of the plane with copies of any shape is called rigid (or "stable") if every unit is fixed by its neighbors, i.e., no unit ...

1
vote

0
answers

83
views

### cone structure of complement of hyperplanes

I want to know if in $\mathbb{R}^{m+3}$ we consider the following hyperplanes:
\begin{cases}
(1-g)y-\sum_{i\in I}x_i=0, & \text{if $I\subset\{1,\cdots,m+2\}$},|I|=g\\
gy-\sum_{i\in I}x_i+\...

33
votes

1
answer

2k
views

### Is there a configuration of 5 points on the plane where any two can be covered by an axis aligned rectangle?

I'm trying to figure out the question in the title for a project that I'm working on.
My goal is to find a configuration of five integer points on the plane, where we can overlap any pair of them ...

2
votes

1
answer

66
views

### Open covering with bounded diameters [closed]

Here is an interesting puzzle I came across.
I have no idea which tools could be applied to solve it, so the tags may be misleading.
For any $A \subseteq \mathbb{R^n}$ , its diameter is defined by
$$\...

9
votes

3
answers

319
views

### Is it possible that every edge in a 1-planar drawing with minimum number of crossings is crossed?

A graph is 1-planar is it has drawing in the plane so that each edge is crossed at most once. Here we also assume the drawing satisfies (1) no edge is self-crossed; (2) no two adjacent edges are ...

1
vote

0
answers

56
views

### Is there any previous study on the relationship between convexity and the order of points in the general position?

Let's assume $V =(v_1,v_2,v_3,… ,v_n)$ is a set points in a general-position. For each point $v_i$, let's list the points in the order we encounter as we rotate around a certain direction (say ...

8
votes

0
answers

277
views

### Fast method to verify if a point belongs to a given convex $d$-polytope

We are given a $d$-dimensional convex polytope $P\in\mathbb{R}^d$. Assume we have all the supporting hyperplanes describing $P$ and its vertices. Let $S$ be a sequence of $n\gg 1$ points $\mathbb{R}^d$...

23
votes

3
answers

3k
views

### Polyomino that can cover an arbitrarily large square but not the entire plane

https://userpages.monmouth.com/~colonel/nrectcover/index.html
For a polyomino with no holes that cannot tile the plane, we may ask what are the maximal rectangles and infinite strips that it can ...

7
votes

0
answers

155
views

### Tiling space with supertile of hypercube unfoldings

Two students in my class
asked and answered what might be a novel question.
It is well known that the cube has exactly $11$ edge-unfoldings
(or "nets"), as shown below:
(Image from ...

4
votes

3
answers

203
views

### Existence of (near) equidistant codewords

My question is originally related to coding theory, but fairly easy to state in pure combinatorial way.
Fix $k\in\mathbb{N}$, $\beta\in(0,1)$ and consider the binary cube $\Sigma_n = \{0,1\}^n$ ...

0
votes

1
answer

44
views

### Bounds on the number of samples needed to learn a real valued function class

Let us see Theorem 6.8 in this book, https://www.cs.huji.ac.il/w~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf
It gives us a lowerbound (and also an ...

14
votes

4
answers

1k
views

### A notion of 2-dimensional tree

Summary: This post has got rather long after the discussion. The main still open Questions are 5 & 6 below. There is work in progress, and I'll post an update at some point.
A tree is a connected ...

1
vote

0
answers

40
views

### When can infinite graphs be partitioned into trees of a given minimum size

Let $G=(V,E)$ be a graph with $0<\#V\leq \#\mathbb{N}$ and fix $n\leq \#V$. When can $G$ be partitioned into $(V_1,E_1),\dots,(V_m,E_m)$ where $V= \cup_i \, V_i$, $\#V_i\geq n$ and $E_i$ contains ...