# Questions tagged [discrete-geometry]

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

1,585
questions

11
votes

0
answers

105
views

### Can the optimal packing density in $\mathbb{Z}^d$ be irrational?

For a finite $S \subset \mathbb{Z}^d$, let $d_p(S)$ be its optimal packing density. That is, the maximal lower asymptotic density of $A+S$, where $A \subset \mathbb{Z}^d$ is such that $(a_1+S)\cap (...

3
votes

2
answers

156
views

### Random walk to visible lattice points

Consider a random walk from the $\mathbb{Z}^2$ origin $(0,0)$ to visible
(not blocked) lattice
points $p$, with a parameter $r$ a given radius of a circle centered
on $p$.
With $p$ the previous point, ...

3
votes

1
answer

318
views

### Illumination from visible lattice points with inverse square intensity

It is well known that the number of $\mathbb{Z}^2$ lattice points visible from
the origin is $6/\pi^2$, about $61$%.
See, e.g.,
What fraction of the integer lattice can be seen from the origin?.
I am ...

2
votes

0
answers

52
views

### Connected geometric thickness two

A graph $G = (V,E)$ has geometric thickness two if there exists an embedding $\varphi: V \rightarrow \mathbb{R}^2$ and a decomposition $E = E_1\cup E_2$ such that $G_1 = (V,E_1)$ and $G_2 = (V,E_2)$ ...

3
votes

0
answers

29
views

### Minimum number of common edges of triangulations

Let $S$ and $T$ be two triangulations.
We define
$c(S,T)$ as the number of edges shared by $S$ and $T$.
With this, we can define
$f(n) = \min_{P} \min_{S,T} c(S,T)$.
Here the first minimum goes over ...

4
votes

1
answer

235
views

### Does Kalai's $3^d$ conjecture hold for simplicial spheres?

Kalai's $3^d$ conjecture asserts that every centrally symmetric $d$-polytope has at least $3^d$ non-empty faces. This is open in general, but has been proven for simplicial polytopes.
Question: Does ...

3
votes

0
answers

100
views

### Divide Euclidean space by surfaces

It is well known that $n$ hyperplanes in $\mathbb{R}^k$ can divide $\mathbb{R}^k$ into at most $p$ regions where $p$ is
\begin{equation}
1 + n + C^2_n + \cdots + C^k_n
\end{equation}
Is there similar ...

4
votes

2
answers

129
views

### On the number of intersection points between a curve and a (horizontal, vertical) line inside a unit square

I am looking for a reference (name, source) of the following elementary geometric combinatorial problem:
Inside a unit square, given a smooth curve of length $L$. Then there exists a horizontal or ...

0
votes

0
answers

64
views

### Frameworks in general position that are locally rigid but not infinitesimally rigid

The classical theorem of Asimow and Roth says that for a generic framework (i.e., coordinates of the nodes are algebraically independent), local rigidity and infinitesimal rigidity are equivalent. I ...

1
vote

1
answer

77
views

### The problem of finding the smallest number of copies of a certain shape that can be placed into a space to make fitting another copy impossible

Packing problems often ask for the largest number of some identical shape that can fit in a given space without overlapping, if they are placed optimally.
I'm interested in the opposite question:
Q. ...

4
votes

0
answers

104
views

### Advice on results for balls on regular $N$-dimensional grids

I have obtained some results regarding balls on regular $N$-dimensional grids. I would like expert opinion on wether the results are significant or interesting enough for (trying to) publish them in a ...

0
votes

0
answers

152
views

### Sum of square of parts, and sum of binomials over integer partition

Let $n$ be positive integer. Consider its integer partitions denoting as $(m_1,\cdots,m_k)$, where $m_1+\cdots+m_k=n$ and the order does not matter. We ignore the case of $(m_1,\cdots,m_k)=n$.
I am ...

0
votes

0
answers

37
views

### 3d convex body with max kissing number with translates

Ref: Convex region $C$ with least kissing number of copies of $C$
Given a convex body $C$, let us define its 'translate kissing number' $k_t$ as the largest possible number of translated copies of $C$ ...

1
vote

0
answers

17
views

### The optimal embedded and enclosing cardioids for a triangle

Ref: https://en.wikipedia.org/wiki/Cardioid
Earlier posts with similar questions: Smallest 3-ellipses that contain triangles and Curves of constant width that contain triangles
Questions: Given any ...

38
votes

0
answers

657
views

### Can a regular icosahedron contain a rational point on each face?

The title says it all: Is there a (regular) icosahedron containing a rational point on each of its faces?
For other Platonic solids, the affirmative answer is easy. Indeed, regular tetrahedra, cubes, ...

3
votes

0
answers

89
views

### Minimal set of geometric moves in various equivalence classes of triangulated geometries

I would like to get to know what is the minimal set of geometric changes "aka. moves" (topology preserving modifications / Pachner moves / bistellar moves) that can transform any 3-...

0
votes

0
answers

84
views

### Which polytopes can be folded to an edge?

While playing with bar-and-joint linkages, I noticed that the skeleton of a regular 3-dimensional cube can be folded to a single edge (this can be achieved by first flexing the cube to bring it to a ...

1
vote

0
answers

41
views

### Which rectangles can be cut into mutually non-congruent rectangles all of same diagonal length?

This earlier post asks, among other things, whether the plane can be tiled with mutually non-congruent rectangles all of which have same length of diagonal: Tiling the plane with mutually non-...

2
votes

0
answers

96
views

### Minimum number of points on sphere which cannot be covered by three double caps

What is the minimum number of points on the sphere $S^d \subset \mathbb{R}^{d+1}$ which cannot be covered by $d+1$ double caps? A double cap is defined to be a set $\{x \in S^d: |\langle x,a \rangle| &...

3
votes

1
answer

84
views

### Does a matroid base polytope contain its circumcenter?

Let $(X,\mathcal B)$ be a matroid on the ground set $X=(x_1,...,x_n)$ and with set of bases $\mathcal B$, and let $P\subset\Bbb R^n$ be its matroid base polytope (i.e. the convex hull of the ...

4
votes

0
answers

69
views

### Which rectangles can be cut into finitely many rectangles all with same perimeter and different areas?

Ref 1: dividing a square into unique rectangles with the same perimeter
https://arxiv.org/ftp/arxiv/papers/1307/1307.3472.pdf
Ref 1 asks if a square can be cut into some finite number of rectangles ...

0
votes

0
answers

24
views

### Convex 3d bodies for which all planar sections with max diameter have same diameter

Ref:
1.
A claim on planar sections of 3D convex bodies
On convex 3d bodies whose shadows are all of constant diameter
Given a 3D convex body $C$ and a specified direction $n$, we consider the planar ...

3
votes

0
answers

81
views

### On convex 3d bodies whose shadows are all of constant diameter [closed]

We add a bit to More on shadows of 3D convex bodies
By a shadow of a 3D body, we mean the orthogonal projection of it onto a 2D plane.
If all shadows of a convex 3D body have the same diameter, will ...

10
votes

1
answer

449
views

### A projective plane in the Euclidean plane

Problem. Is there a subset $X$ in the Euclidean plane such that $X$ is not contained in a line and for any points $a,b,c,d\in X$ with $a\ne b$ and $c\ne d$, the intersection $X\cap\overline{ab}$ is ...

0
votes

1
answer

39
views

### On largest convex m-gons contained in a given convex n-gon where m < n

This post is the inside-out variant of On smallest convex m-gons that contain a given n-gon where m<n
Given a convex n-gon region P, and an m less than n, how to find the max area convex m-gon Q ...

1
vote

0
answers

108
views

### The number of incidences between points and parabolas on $\mathbb{R}^2$

I was reading Adam Sheffer's book "Polynomial Methods and Incidence Theory" and I tried to solve the following exercise:
Exercise 1.1 Construct a set $\mathcal{P}$ of $m$ points and a set $\...

0
votes

0
answers

78
views

### On smallest convex m-gons that contain a given n-gon where m<n

Given a convex n-gon region P, and an m less than n, will the least area convex m-gon Q that contains P be such that an edge of Q coincides with an edge of P (in other words Q cannot be such that P ...

1
vote

0
answers

46
views

### On points in the interior of planar convex regions and inscribed triangles

Given any planar convex region C, it is easy to show that every point in the interior C is the mid point of at least one chord of C. Likewise,
Question: Is every point in the interior of C the ...

1
vote

0
answers

37
views

### Locality and restriction properties for self-avoiding and loop-erasing random walks

This question has been cross-posted from math.stackexchange.com : https://math.stackexchange.com/questions/4742746/locality-and-restriction-properties-for-self-avoiding-and-loop-erasing-random-wa
I ...

11
votes

1
answer

497
views

### A variant of the corners problem

Question: What is the size of the largest subset of $[n]^2$ containing no three point configurations of the form $(x,y), (x,y+d), (x+d,y')$ with $d \neq 0$? In particular, is it at most $O(n)$?
Recall ...

1
vote

1
answer

65
views

### When do the centers of mass of a uniform convex planar region as a whole and of its boundary alone coincide?

Given a uniform planar convex region C, let us consider 2 centers of mass - the center of mass of the region as a whole and the center of mass of its boundary alone (assuming its boundary to have ...

0
votes

0
answers

135
views

### Equivalent formulation of Szemerédi-Trotter theorem

I am reading the first chapter of Adam Sheffer's book "Polynomial Methods and Incidence Theory" and in Lemma 1.15 he proves an equivalent formulation of Szemerédi-Trotter theorem. Before ...

6
votes

0
answers

118
views

### Have the affine simplicial line arrangments been enumerated?

I am looking for a classification (or attempt at enumeration) of affine simplicial line arrangements.
A line arrangment is a family of straight lines in $\Bbb R^2$. It is simplicial if all regions are ...

8
votes

2
answers

464
views

### Continuous point map for spherical domains

Consider the space $J$ of Jordan domains on the sphere $\textbf{S}^2$, i.e., continuous injective maps from the unit disk into $\textbf{S}^2$ modulo homeomorphisms of the disk. How can one construct a ...

2
votes

1
answer

122
views

### Planar convex region maximizing the difference in 'orientation' between its smallest containing rectangle and largest contained rectangle

We say a rectangle has orientation $\theta$ if the vector from its center to the middle of its shortest side (parallel to the longest side) has some angle $\theta$ with X axis.
Consider a planar ...

1
vote

1
answer

72
views

### To optimally wrap convex laminae with paper

Ref: On folding a polygonal sheet, Multi-layered wrapping of polyhedra
Basic intent: to wrap a given convex planar lamina with a convex sheet of non-stretchable paper (such that every point on both ...

4
votes

0
answers

196
views

### What does it mean "parallel"?

I am thinking on a strict definition of the notion of parallel affine sets in a linear space and came to the following
Definition 1: An affine set $A$ is parallel to an affine set $B$ in a linear ...

8
votes

3
answers

718
views

### Alternating Sum Involving Catalan Numbers

I was wondering if anyone knew how to obtain a simpler closed form of the following sum(or had any other insights regarding it):
$$\sum_{k=0}^n (-1)^k{n \choose k} C_{2n-2-k} $$
Here $C_n = \frac{1}{n+...

1
vote

0
answers

143
views

### Membership test of convex set

Let $K$ be a compact convex subset of $R^n$ which has some positive gaussian measure, say at least 1/2. For each nonzero vector $u \in R^n$, we
define another compact convex set $K * u$ in the ...

2
votes

0
answers

53
views

### A claim on planar sections of 3D convex bodies

Ref: More on shadows of 3D convex bodies,
Shadows and planar sections of polyhedra
Given a 3D convex body C, we define a maximal area (perimeter) section of C with respect to any specified direction $...

2
votes

0
answers

97
views

### More on shadows of 3D convex bodies

Ref: Shadows and planar sections of polyhedra
By shadow we mean the orthogonal projection of a convex 3D body C onto a 2D plane, for example, the shadow on the xy-plane, with C above (z>0) that ...

5
votes

1
answer

107
views

### Beating trivial bound for $k$-AP-free sets in characteristic $k$

Given integers $k,n\ge 1$, I shall write $\Bbb{Z}_k^n := (\Bbb{Z}/k\Bbb{Z})^n$.
Fix $k\ge 3$. Let $r_k(\Bbb{Z}_k^n)$ denote the cardinality of the largest $A\subset \Bbb{Z}_k^n$, such that $A$ does ...

2
votes

1
answer

66
views

### On convex solids with all plane sections affine congruent

Question: How many (classes of) convex 3D solids are there such that all non-degenerate planar sections of the solid are mutually affine congruent?
Further question: Same as above with 'projective' ...

2
votes

1
answer

56
views

### Calculating a relaxed Delaunay Triangulation

The triangles of a planar Delaunay Triangulations are essentially characterized by the property that no triangle's corner is inside another triangle's circumcircle; Delaunay Triangulations can be ...

1
vote

2
answers

86
views

### A claim on concurrency of 'Width Bisectors' of planar convex regions

We add a bit to A claim on the concurrency of area bisectors of planar convex regions
Define a width of a planar convex region $C$ as the distance between two parallel lines that just touch $C$. A ...

2
votes

0
answers

86
views

### Real-isability of a (relatively small) subconfiguration of the Klein configuration

The Klein configuration consists of $60$ points and $60$ planes in $\mathbb C\mathbf P^3$, each point lying on $15$ of the planes and each plane containing $15$ of the points. It appears, among many ...

1
vote

0
answers

57
views

### Intercept theorem in $\mathbb R^n$

The celebrated intercept theorem(also known as Thales's theorem) provides the ratios between the line segments created when two parallel lines are intercepted by two intersecting lines.
I'm looking ...

1
vote

0
answers

34
views

### On partitioning convex polygonal regions in area ratio $t : (1-t)$ where $0<t<1/2$ with least length of cut

Question: Given a convex n-gon P. How can we efficiently find the partition of P into 2 pieces with areas in the some given ratio $t : (1-t)$ where $0<t<1/2$ such that the length of cut is ...

1
vote

2
answers

89
views

### Are there variants of Euclidean Steiner Tree problem that are known to be in P?

Question: The Euclidean Steiner Tree problem (https://en.wikipedia.org/wiki/Steiner_tree_problem) is NP hard. Are there non-trivial (constrained) variants of this question that are known to have ...

8
votes

2
answers

540
views

### Three-dimensional triangulations with fixed number of vertices

My question is the following:
Are there triangulations of $S^3$ which (a) are non-degenerate, (b)
have four vertices, and (c) have no edges of degree two?
A side question:
If one represents this ...