Questions tagged [discrete-geometry]
Finite or discrete collections of geometric objects. Packings, tilings, polyhedra, polytopes, intersection, arrangements, rigidity.
1,815
questions
10
votes
3
answers
481
views
Given the skeleton of an inscribed polytope. If I move the vertices so that no edge increases in length, can the circumradius still get larger?
Let $P\subset \Bbb R^n$ be an inscribed convex polytope, that is, all its vertices are on a common sphere of radius $r$.
Let $G$ be the edge-graph of $P$. For convenience, assume $V(G)=\{1,\dotsc,s\}$....
4
votes
0
answers
54
views
On ways to measure the difference between two planar convex regions
This earlier post attempted to quantify the difference between a pair of planar convex regions of equal area and perimeter using Hausdorff distance:
On comparing planar convex regions of equal ...
3
votes
1
answer
131
views
Finding the smallest centrally symmetric region that contains a convex planar region
Given a convex polygonal region C, how does one find/characterize the smallest zonogon (centrally symmetric convex polygon https://en.wikipedia.org/wiki/Zonogon) that contains C?
Note 1: In question ...
1
vote
0
answers
72
views
A ratio to measure 'roundedness' of planar convex regions
Ref: A center of convex planar regions based on chords
The above discussion quotes the definition of 'centralness coefficient' and defines a center of a planar convex region. 1/2 is the least possible ...
2
votes
0
answers
71
views
On cutting convex regions with average values of quantities minimized
This post continues from Cutting convex regions into equal diameter and equal least width pieces - 2 and Cutting convex regions into equal diameter and equal least width pieces - 3
A basic (and to my ...
4
votes
0
answers
121
views
Find a good drawing for the edges of any two component of $G-S$ that do not cross
A drawing of a graph $G$ on the plane $P$ is a representation of $G$, where vertices are distinct points in $P$, and edges are Jordan arcs in the plane joining the points corresponding to their end ...
8
votes
1
answer
400
views
What should a meaningful notion of curvature satisfy, in the absence of a smooth structure?
There are many generalizations of various curvatures to non-smooth metric spaces (e.g. Ollivier's Ricci curvature). Suppose I have a metric space $(X,d)$ and I want to define a notion of curvature ...
3
votes
0
answers
69
views
On possible generalizations of the Steiner ellipse – convex regions containing and contained within a given convex quadrilateral
In the post On convex regions containing (and contained within) a given triangle , it was noted:
for a general triangle $T$, the convex region $C_M$ of largest area containing $T$ such that $T$ is ...
3
votes
2
answers
201
views
Partition of polygons into 'congruent sets of polygons'
Definition: Two finite sets of polygons $A$ and $B$ are congruent if we can match polygons in $A$ in a one-one manner with polygons in $B$ with each matched pair of polygons mutually congruent.
...
0
votes
0
answers
81
views
Perfectly balanced spanning trees
I call a spanning tree perfectly balanced if, after a two-coloring of the tree-graph's vertices
the two vertex sets that are defined by the assigned colors have equal cardinality and
the two vertex ...
3
votes
1
answer
223
views
Least area and least perimeter triangles that contain a convex planar region - how different can they be?
Is there a planar convex region whose enclosing triangles of least perimeter and least area have different areas and different perimeters? And if so, which region maximizes the difference between the ...
2
votes
1
answer
78
views
What is the average component size of a coloring?
Supose each cell of a big (or infinite) grid is colored at random by one of $k$ colors. Then the connected monochromatic components (here components are not supposed to contain "wasp waists",...
9
votes
1
answer
347
views
Tiling the plane with finitely many congruent pieces
Suppose $A_1,\dots,A_n$ are measurable subsets of the plane that are all related by rigid motions such that $|(A_1 \cup \dots \cup A_n)^c| = 0$ and $|A_i \cap A_j| = 0$ for all $1 \leq i < j \leq n$...
1
vote
0
answers
30
views
On partitioning n-gons into pieces with reflection symmetry
Is 3(n-2) a tight lower bound on the least number of reflection symmetric pieces that any general n-gon can be cut into? What if we consider only convex n-gons?
A kite is a reflection symmetric ...
13
votes
3
answers
651
views
Are there Monohedra with odd numbers of faces?
A monohedron is a convex polyhedron with all faces mutually congruent but with no other symmetry necessarily needed. So obviously, this is a wide class of polyhedra that includes the Platonic solids ...
3
votes
0
answers
118
views
Oscillator in Langton's ant
First of all, see Langton's ant Wikipedia page.
If we place a pair of ants looking north (using Golly or any another prog) on the coordinates $(x_1,y_1)$ and $(x_2,y_2)$ under the conditions:
$p=|x_1-...
5
votes
2
answers
305
views
Dimension of configuration space of triangulated convex polyhedron
The configuration space of all tetrahedra is $5$-dimensional, perhaps a non-obvious fact.
There are $12$ face angles, but the sum of each of the four faces angles is $\pi$,
reducing $12$ to $8$ ...
2
votes
1
answer
146
views
Packing densities of non-centrally symmetric planar convex regions
Reference: https://en.wikipedia.org/wiki/Smoothed_octagon
Background: The smoothed octagon is conjectured to have the lowest maximum packing density of the plane of all centrally symmetric convex ...
3
votes
0
answers
274
views
Polyhedrons and their centers of mass
Given a convex polyhedron, one considers 3 possibilities:
wireframe - only the edges of the polyhedron have mass which is uniformly distributed.
surface - only the surface is massive with uniform ...
2
votes
0
answers
61
views
Rigid monohedral tilers
Say that a tile $T$ that alone can tile the plane—a monohedral tile—is rigid
if it is not the case that $T$ can be slightly deformed to $T'$ so that:
$T'$ can also tile the plane
$T'$ is arbitrarily ...
1
vote
1
answer
501
views
Has this curious "duality" of weighted $K_4$ already been noticed?
A complete symmetric graph with $n=4$ vertices, i.e. a $K_4$ is the disjoint union of three perfect matchings $M_{\text{min}},M_{\text{mid}},M_{\text{max}}$ of which $M_{\text{min}}$ denotes the ...
24
votes
1
answer
590
views
Polytope where each vertex belongs to all but two facets
Let $P$ be a (convex, bounded) polytope with the following property: for every vertex $v$, there are exactly two facets which do not contain $v$. Does it follow that $P$ is (combinatorially) a ...
1
vote
0
answers
52
views
Shadows and planar sections of polyhedra – 2
This post continues Shadows and planar sections of polyhedra and On planar sections of 3D convex bodies
Shadows and planar sections of polyhedra gives an example demonstrating that shadows (orthogonal ...
4
votes
1
answer
207
views
Shadows and planar sections of polyhedra
By shadow we mean the orthogonal projection of a convex 3D body P onto a 2D plane, for example, the shadow on the xy-plane, with P above (z>0) that plane and the light at L=(0,0,+∞). P an be freely ...
2
votes
0
answers
102
views
A Variant of the Malfatti Problem
See the Wikipedia entry on Malfatti circles for an introduction to Malfatti's problem.
The above page also states that for $n >3$, the question of whether a greedy method (at each step, the method ...
5
votes
1
answer
130
views
Embedding linklessly embeddable graphs without Borromean rings
A linklessly embeddable graph is a graph which can be embedded into $\Bbb R^3$ so that no two of its cycles are linked. For example, the Petersen graph is not such a graph.
Now, I can think of another ...
5
votes
2
answers
227
views
On intersections of several convex regions
Question: Given n convex planar regions. Required to place them (in suitable position and orientation) so that that part of the plane lying under all the regions (their common intersection) is of ...
9
votes
1
answer
282
views
Partitioning a set of lattice points in the plane into rectangles
The "long comment" by Pietro Majer on Reference for puzzle on dividing piles and scoring products suggests the
following problem. Let $S$ be a finite subset of $\mathbb{Z}\times
\mathbb{Z}$. ...
7
votes
0
answers
223
views
Set of unit vectors such that among any three there is an orthogonal pair
I was fascinated by the solutions of Problem 8 of the IMC 2021 contest, which can be summarized as:
Theorem 1. Let $v_1,\dotsc,v_N$ be distinct unit vectors in $\mathbb{R}^n$ such that among any three ...
5
votes
2
answers
292
views
Tiling a Jordan polygon
I saw this problem some years ago, don't remember the source:
Let $P$ be a Jordan polygon (i.e. the only points of the plane belonging to two edges are the polygon vertices) that can be tiled with ...
-3
votes
1
answer
811
views
combinatoric proof $\sum_{i=0}^{n}(-1)^i\binom{n}{i}\binom{n-i+k-1}{k}=\binom{k-1}{k-n}$ [closed]
I would like help with combinatorial proof ,
not algebraic proof . Thank you for your time
$\sum_{i=0}^{n}(-1)^i\binom{n}{i}\binom{n-i+k-1}{k}=\binom{k-1}{k-n}$
1
vote
0
answers
46
views
Uniformization of triangulation on a sphere up to Moebius transformations
This is not the most precise question but rather a hope that someone has seen something like this.
I am given a triangulation of the 2-sphere $S^2$ which I only know up to Moebius transformations. I ...
3
votes
1
answer
307
views
Planar subsets with many pairs of points on distance $1$ [duplicate]
Let $X$ be a subset of $\mathbb R^2$ consisting of $n$ distinct points. Let $d_1(X)$ be the number of pairs of points of $X$ on distance $1$ from each other. Define
$$d_1(n)=\sup_{X\subset \mathbb R^2|...
6
votes
2
answers
423
views
On planar sections of 3D convex bodies
Consider the space of planar sections of any given convex 3D body.
Basic Question: What is the lower bound for the ratio
$$\frac{\text{area of section of greatest perimeter}}
{\text{area of section of ...
4
votes
2
answers
289
views
Which convex pentagon gives least packing density?
Among all convex pentagons, does the regular pentagon give least packing density?
Further question: For each $n > 6$, is the regular $n$-gon the minimum of packing density?
An analogous question ...
1
vote
0
answers
67
views
Facility location and traveling salesman
This question is based on Distributing points evenly on a sphere and Facility location on manifolds
The 'dispersal problem' (which can be mapped to packing disks in many cases) places $n$ points in a ...
8
votes
1
answer
145
views
The polytope algebras generated by polytopes with rational vs arbitrary vertices
The polytope algebra was defined by P. McMullen in "The polytope algebra" Adv. Math. 78 (1989) as follows.
Let us denote by $\Pi'_\mathbb{R}$ the quotient of the free abelian group generated ...
4
votes
0
answers
111
views
Projective planes over algebraically closed fields
Suppose I am given a projective plane $P \cong \mathbb{P}^2(k)$ over a (commutative) field $k$.
With "projective plane," I mean the point-line geometry (and not, for instance, the scheme): $...
1
vote
3
answers
142
views
On packing axisymmetric bodies in 3D
Consider any 3D body with an axis of rotational symmetry (e.g. cone, cylinder...) and packing the 3d space efficiently with infinitely many copies of this body. Is the following claim valid?
Claim: ...
21
votes
3
answers
895
views
Cutting of a regular polygon into congruent pieces
Question. For which $N$ it is possible to cut a regular $N$-gon into congruent pieces such that the center of the regular polygon lies strictly inside one of the pieces? For $N=3,4$ there are trivial ...
4
votes
1
answer
140
views
How many regular d-dimensional simplices of side length 1/2 are required to cover a regular d-dimensional simplex of side length 1?
For positive integers $n$ and $d$ satisfying $d = n-1$, let the $d$-dimensional regular simplex of side-length $\sqrt{2}$ be $X = \{(x_1, x_2, \cdots, x_n) \in \mathbb{R}^n: x_1+x_2+\cdots + x_n = 1, ...
0
votes
0
answers
52
views
What do optimal tours tell about finite point sets?
Let $T_{\mathrm{MIN}}$ and $T_{\mathrm{MAX}}$ denote the shortest, resp. longest Hamilton cycle through a set of $n=2k+1$ points.
Let further $S_{\mathrm{MIN}}$ and $S_{\mathrm{MAX}}$ be the "...
8
votes
1
answer
311
views
Are there any convex pentagonal rep-tiles?
A rep-tile is a shape that can tile larger copies of the same shape.
Question 1: Are there any convex pentagons that are also rep-tiles?
Remarks: 15 convex pentagonal tiles of the plane are known and ...
15
votes
2
answers
763
views
Three squares in a rectangle
One of my colleagues gave me the following problem about 15 years ago:
Given three squares inside a 1 by 2 rectangle, with no two squares overlapping, prove that the sum of side lengths is at most 2. (...
1
vote
0
answers
121
views
A center of convex planar regions based on chords
This is based on Chapter 6 of 'Convex figures' by Yaglom and Boltyanskii. This post also continues On two centers of convex regions.
A point $P$ in the interior of a planar convex region $C$ divides ...
1
vote
0
answers
45
views
Multi-layered wrapping of polyhedra
This post continues from How big a box can you wrap with a given polygon? and Convex polyhedra that can be folded from convex polygons. One can also mention 'k-fold coverings of the plane' as examined ...
2
votes
1
answer
108
views
Convex polyhedra that can be folded from convex polygons
This question is based on http://www.science.smith.edu/~jorourke/Papers/FoldingPP.pdf.
Therein is stated the theorem: Every convex polygon folds to an infinite number (a continuum) of noncongruent ...
2
votes
0
answers
863
views
Happy ending problem – Why not a proof by induction?
I have been thinking for a while on the happy ending problem, looking for approaches to attack the Erdős–Szekeres conjecture: the smallest number of points for which any general position arrangement ...
6
votes
0
answers
219
views
How big a box can you wrap with a given polygon?
Question: Given a convex polygonal region, how does one find the box (rectangular parallelopiped) of maximum volume that can be wrapped with this region? While wrapping, if needed, some portions of ...
3
votes
1
answer
133
views
Covering radius of a lattice from relevant vectors
Let $L$ be an $n-$dimensional lattice. The Voronoi region of $L$ is given by
$$
\mathcal{V}(L)=\big\{x\in\mathbb{R}^n~|~ \|x\|_2\leq \|x-v\|_2~\forall v\in L\setminus\{0\}\big\}.
$$
Considering the ...