Questions tagged [discrete-geometry]
Finite or discrete collections of geometric objects. Packings, tilings, polyhedra, polytopes, intersection, arrangements, rigidity.
1,819
questions
5
votes
1
answer
111
views
Finding the point within a convex n-gon that maximizes the least angle subtended there by an edge of the n-gon
For any point P in the interior of a convex polygon, the sum of the angles subtended by the edges of the polygon is obviously 2π.
Given a convex polygon, how does one algorithmically find the point (...
1
vote
0
answers
14
views
Finding the point within a convex n-gon that minimizes the largest angle subtended there by an edge of the n-gon
This post records a variant to the question asked in this post: Finding the point within a convex n-gon that maximizes the least angle subtended there by an edge of the n-gon
Given a convex n-gon, ...
0
votes
0
answers
49
views
An algorithm to decide whether a convex polygon can be cut into 2 mutually congruent pieces
This post is based on the answer to this question: A claim on partitioning a convex planar region into congruent pieces
A perfect congruent partition of a planar region is a partition of it with no ...
0
votes
0
answers
23
views
Is there a variant of the crossing lemma for multigraphs with arbitrary embedding?
Suppose $G$ is a graph with $m=|E(G)|$ edges and $n=|V(G)|$ vertices.
Suppose $sim(G)$, the simplification of $G$ contains $ m' >> 3n $ edges.
Call the set of edges corresponding to an edge $uv$...
1
vote
0
answers
75
views
To tile the plane with mutually non-congruent rational triangles of equal area
We add a little to Tiling the plane with pairwise non-congruent rational triangles
Question: Can the plane be tiled by pair-wise non-congruent rational triangles all of which have same area? If "...
1
vote
1
answer
198
views
On comparing planar convex regions of equal perimeter and area
Definitions:
The Hausdorff distance between two point sets is the greatest of all the distances from a point in one set to the closest point in the other set.
Given two planar convex regions $C_1$ ...
2
votes
0
answers
75
views
"separators" for nonplanar graphs embedded in the plane
Given a nonplanar graph $G$ drawn in the plane with crossings.
Does there exist a small subset $S$ of edges of $G$ such that after the removal of all edges that intersect or share an endpoint of an ...
1
vote
1
answer
215
views
Positioning a member of an interval partition
Let $\ 0<\Lambda_1\le\ldots\le\Lambda_n\ $ be a finite non-decreasing sequence of positive reals, of length $\ n>0.\ $ Let
$$ D:=\sum_{k=1}^n \Lambda_k $$
The question is about the conditions ...
11
votes
0
answers
308
views
Is a convex polyhedron determined by its edge lengths and angular defects?
Let's consider 3-dimensional convex polyhedra $P\subset\Bbb R^3$.
The angular defect at a vertex $v$ is $2\pi$ minus the sum of the interior angles of the incident faces at $v$.
Question:
Is a ...
2
votes
1
answer
130
views
Do the dual graphs of hyperplane arrangements admit Hamiltonian paths?
Consider a simple hyperplane arrangement $H_1,\cdots,H_n$ in the Euclidean space $\mathbb{R}^d$. By "simple" we mean any $k$ hyperplanes in $\{H_1,\cdots,H_n\}$ intersect in codimension $k$. ...
4
votes
1
answer
414
views
Counting number of points on a lattice in a hypercube
Suppose I have a lattice $\Lambda \in \mathbb{R}^n$. Let $X_i >0$ for $i=1,..,n$. I am interested in some references regarding counting number of points of $\Lambda$ inside $[-X_1, X_1] \times \...
8
votes
1
answer
250
views
A claim on partitioning a convex planar region into congruent pieces
Let us define a perfect congruent partition of a planar region $R$ as a partition of it with no portion left over into some finite number n of pieces that are all mutually congruent (ie any piece can ...
1
vote
0
answers
38
views
Polyhedra inscribed in a sphere with mutually non-congruent, equal area faces
Two constrained versions of the main question given in this post: Polyhedrons with mutually non-congruent faces, all of equal area. An earlier post that could be related: Cutting a spherical surface ...
3
votes
1
answer
185
views
Exponential growth of shortest vector norm for successive lattices corresponding to powers of a matrix
Let $A\in M_{2\times 2}(\mathbb{Z}) $ be a two by two integer matrix such that $0,\pm 1$ are not eigenvalues of $A$ and $\left|\det(A)\right|>1$. I am interested in the growth of the norm shortest ...
5
votes
1
answer
387
views
Computational approach deciding whether a set of Wang Tile could tile the space up to some size
As an applied person, I'm facing one practical problem deciding whether a set of Wang tile could tile the plane periodically or aperiodically. Although both problems seem undecidable, but I'm on a ...
4
votes
0
answers
104
views
Hyponontiling Wang tiles
Call a finite collection of tiles that can tile the plane if we have to use each tile at least once tiling.
Is there a collection of at least 3 tiles that is not tiling, but such that after removing ...
1
vote
0
answers
82
views
Polyhedrons with mutually non-congruent faces, all of equal area
This question is closely related to Convex polyhedra with non-congruent faces
It is known that if all faces of a tetrahedron ought to have same area (or same perimeter), then, the faces are ...
1
vote
0
answers
28
views
Finite right-triple convex sets in planes
Let $\mathcal{S}$ be a set of points in $\mathbb{R}^2$. We say that $\mathcal{S}$ is right-angle convex, if for any two distinct points $P,Q\in \mathcal{S}$ there always exists another point $R\in \...
18
votes
1
answer
1k
views
Does a function from $\mathbb R^2$ to $\mathbb R$ which sums to 0 on the corners of any unit square have to vanish everywhere?
Does a function from $\mathbb{R}^2$ to $\mathbb{R}$ which sums to 0 on the corners of any unit square have to vanish everywhere?
I think the answer is yes but I am not sure how to prove it.
If we ...
10
votes
1
answer
259
views
Do triple-linked graphs exist?
Lets say that a finite simple graph $G$ is (intrinsically) fully triple-linked if for each embedding of $G$ into $\Bbb R^3$ we can find three disjoint cycles $C_1,C_2,C_3\subset G$ whose embeddings ...
16
votes
0
answers
289
views
Realization spaces of 3-dimensional polytopes with fixed face areas
It is a well-know result (Steinitz, 1922) that the realization space of 3-dimensional convex polytopes with fixed combinatorics is contractible.
A proof of this theorem can be found for instance in ...
0
votes
0
answers
69
views
Heronian tetrahedra with pairwise non-congruent, equal area faces
Reference: https://mathworld.wolfram.com/HeronianTetrahedron.html lists some Heronian tetrahedra that are disphenoids.
Are there any Heronian tetrahedra with all faces having same area but are ...
1
vote
1
answer
106
views
Recognizability/unique composition property for substitution tiling
This may be a very basic question, but I have not found an answer to it so far in my search. The question is whether there is an "algorithmic" way to check unique-composition/recognizability ...
1
vote
0
answers
90
views
A claim on the largest area circular segment that can be drawn inside a planar convex region
This post adds a little to To find the longest circular arc that can lie inside a given convex polygon
A circular segment is formed by a chord of a circle and the line segment connecting its endpoints....
28
votes
3
answers
2k
views
Is the ratio Perimeter/Area for a finite union of unit squares at most 4?
Update: As I have just learned, this is called Keleti's perimeter area conjecture.
Prove that if H is the union of a finite number of unit squares in the plane, then the ratio of the perimeter and ...
3
votes
1
answer
670
views
Infinite dimensional lattice for integers and the Riemann hypothesis?
It is known that for each finite set of primes $p$ we have: $\log(p)$ are linear independent over the rational numbers.
We have $\log(ab) = \log(a)+\log(b)$ and $\log(n) = \sum_{p |n}v_p(n) \log(p)$.
...
1
vote
1
answer
87
views
To place copies of a planar convex region such that number of 'contacts' among them is maximized
A contact between two planar convex regions obviously happens either along a line segment or at a single point.
Question: Given a planar convex region $C$ and a number $n$, we need to lay out $n$ ...
15
votes
4
answers
844
views
Tiling a rectangle with all simply connected polyominoes of fixed size
For which values of $n$ can we tile some rectangle with one copy of each free simply-connected $n$-omino (that is, each polyomino with $n$ squares that has no holes)?
It appears that it is possible ...
2
votes
1
answer
165
views
Estimating ${\left(\sum_{i=j}^k {x_i}\right)^2} \times \left\lvert\sum_{i=j}^k {a_i}\right\rvert$
Given two sets; $X = \{x_i : x_i \geq 0; i \in [\sqrt{n}]\}$ and $A = \{a_i : |a_i| \leq 1; i \in [\sqrt{n}]\}$ of size $n^{\frac{1}{2}}$ each, with the following properties
\begin{equation}\label{...
12
votes
2
answers
959
views
Drawing 3-configurations of points and lines with straight lines
It is well-known that the black-and-white coloring of the Heawood graph on 14 vertices determines a combinatorial 3-configuration with 7 "points" and 7 "lines", known as Fano plane....
67
votes
3
answers
11k
views
Nonconvexity and discretization
Edit: Here's a more down-to-earth, and somewhat weakened, but I believe still nontrivial, version of the main theorem.
Prototypical nonconvex spaces are $\ell^p$-spaces for $0<p<1$, say $\ell^p(\...
2
votes
1
answer
95
views
Exhaustive list of small graphs for which $\frac{\alpha(G)\omega(G)}{n}$ is small?
I am looking for a list of small graphs (say on less than 10 vertices) for which the parameter $p(G) = \frac{\alpha(G) \omega(G)}{n}$ is small. Here $\alpha(G)$ and $\omega(G)$ is the size of the ...
5
votes
1
answer
139
views
Given a 3-connected graph $G$, is there an edge $e$ so that both $G-e$ and $G/e$ are still 3-connected?
Let $G$ be a 3-connected (simple) graph other than $K_4$. In Diestel's "Graph Theory" Section 3.2 we find
Lemma 3.2.2. There is an edge $e$ so that $G\mathbin{\dot-}e$ is still 3-connected (...
1
vote
1
answer
57
views
To maximize the volume of the polyhedron resulting from perimeter-halvings of a convex polygonal region
We add one more bit to Forming paper bags that can 'trap' 3D regions of max surface area (note: some possibly open related questions are also in the comments following the answer to above ...
2
votes
0
answers
116
views
Folding polygons into 'vessels'
This question is based on http://www.science.smith.edu/~jorourke/Papers/FoldingPP.pdf
Define an vessel as a convex polyhedron with one face removed - in other words, a vessel can be converted into a ...
7
votes
0
answers
128
views
How many simplicial spheres with $n$ vertices and $N$ facets?
Let $s_d(n,N)$ be the number of different $d$-dimensional simplicial spheres on $n$ labelled vertices and $N$ facets (= $d$-simplices). I am in search for the best know upper bounds, especially for $d\...
2
votes
1
answer
165
views
Forming paper bags that can 'trap' 3D regions of max surface area
An existence question based on 'Trapping' 3D regions with sheets of paper.
Given a sheet of paper S that is a planar convex region, one tries to form a 'closed bag' that contains a connected ...
0
votes
0
answers
46
views
Which planar convex region with specified area and perimeter maximizes/minimizes Moment of Inertia?
By moment of inertia of a planar convex region C, here we mean its moment of inertia about an axis passing through the center of mass of C and perpendicular to the plane of C.
Question: For specified ...
3
votes
1
answer
436
views
On some infinite planar arrangements with triangles
Background: Given a convex region C. One can define a graph corresponding to a planar arrangement of non overlapping congruent copies of C - each unit C is a node and an edge connects it to another ...
22
votes
2
answers
878
views
Is every 1-million-connected graph rigid in 3D?
It is an old result that every $6$-connected graph is rigid in $\mathbb{R}^2$:
Lovász, László, and Yechiam Yemini. "On generic rigidity in the plane." SIAM Journal on Algebraic Discrete ...
0
votes
1
answer
121
views
On 'special' points on uniform planar convex regions defined in terms of moment of inertia
The following can be easily proved using perpendicular axes theorem and intermediate value theorem:
Lemma: Given any uniform planar convex region $C$ and any point on it, $P$, there will be at least ...
2
votes
1
answer
194
views
Cutting convex regions into equal diameter and equal least width pieces
The diameter of a convex region is the greatest distance between any pair of points in the region.
The least width of a 2D convex region can be defined as the least distance between any pair of ...
0
votes
0
answers
69
views
On 'Width Equalizers' of planar convex regions
Definitions: The least width of a 2D convex region C is the least distance between any pair of parallel lines that both touch the boundary of C (in what follows, we refer to this quantity as simply '...
6
votes
1
answer
281
views
Covering number estimates on closed Riemannian manifolds
Let $(M^n,g)$ be an $n$-dimensional compact and connected Riemannian manifold with sectional curvature bounded above and below by $c,C$. Is it possible/known how to express the external covering ...
3
votes
0
answers
87
views
Minkowski problem for polytopes: the origin of necessary condition
Minkowski's uniqueness theorem for polytopes concerns the specification of the shape of a polytope by the directions and measures of its facets.
Theorem (Minkowski). Let $A_i$ be positive faces areas ...
21
votes
0
answers
434
views
Does every 5-celled animal tile the plane?
An animal in the plane is a finite set of grid-aligned unit squares in $\mathbb{R}^2$. (The definition is the same as a polyomino, but where we relax the connectivity requirement.) One may ...
38
votes
3
answers
2k
views
Is there a regular pentagon with a rational point on each edge?
This question was asked by Yaakov Baruch in the comments to the question Can a regular icosahedron contain a rational point on each face? It seems that this question deserves special attention.
3
votes
2
answers
758
views
Kepler conjecture: Are there only two most efficient packings or could there be more than two?
Today I attended a talk by Terence Tao, attended by (I'm guessing) probably at least a couple of thousand people, in which among other things he said it had been proved that no packing of spheres in ...
3
votes
0
answers
112
views
Reference request: Carathéodory-type theorem for convex hulls of closed sets
I'm looking for a reference for the following theorem.
Theorem Let $X$ be a closed subset of $\mathbb{R}^N$, and let $a$ be a point of its convex hull $\operatorname{conv}(X)$. Then there exist ...
13
votes
3
answers
414
views
Maximal distance between $2d+1$ points on the $(d-1)$-sphere
If one arranges $2d$ points on the sphere $\mathbf S^{d-1}\subset\Bbb R^d$ at the vertices of the crosspolytope, then one can achieve a minimal spherical distance of $\pi/2$ between any two points, ...