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 (...
- 964
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, ...
- 148k
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 ...
- 148k
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)$ ...
- 439
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 ...
- 439
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 ...
- 11.7k
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 ...
- 79
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 ...
- 41
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,285
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. ...
- 111
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 ...
- 335
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 ...
- 261
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$ ...
- 4,935
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 ...
- 4,935
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, ...
- 21.1k
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-...
- 73
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,285
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-...
- 4,935
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 ...
- 11.7k
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 ...
- 4,935
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 ...
- 4,935
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 ...
- 4,935
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 ...
- 39.6k
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 ...
- 4,935
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 $\...
- 266
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 ...
- 4,935
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 ...
- 4,935
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 ...
- 531
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 ...
- 470
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 ...
- 4,935
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 ...
- 266
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 ...
- 11.7k
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 ...
- 6,654
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 ...
- 4,935
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,935
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 ...
- 39.6k
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+...
- 449
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 ...
- 11
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 $...
- 4,935
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 ...
- 4,935
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,734
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' ...
- 4,935
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 ...
- 12.3k
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 ...
- 4,935
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 ...
- 17.1k
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 ...
- 193
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 ...
- 4,935
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 ...
- 4,935
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 ...
- 73