All Questions
Tagged with reference-request discrete-geometry
174 questions
14
votes
3
answers
2k
views
Optimal wireframe sphere
Suppose you have a length $L$ of metal pipe at your disposal,
and you would like to build a wireframe unit-radius sphere,
by bending, cutting, and welding the pipe into a connected structure $F$.
Your ...
- 63.9k
3
votes
1
answer
381
views
Source on counting lattice points on a line
Looking for a book or article on the result linked below. The result tells us that the number of lattice points on a line between points $(a,b)$ and $(c,d)$ is given by $\gcd(a-c,b-d)+1$.
https://math....
- 198
5
votes
1
answer
190
views
Finding a superbase in a lattice of Voronoi first kind
An $n$-dimensional lattice in $\mathbb R^n$ is said to be of Voronoi’s first kind if it there exists $n+1$ vectors $b_1,\cdots b_{n+1}$ (called the superbase) such that
$\{b_1,\ldots,b_n \}$ is a ...
- 2,183
7
votes
4
answers
377
views
Discretizing a line segment with pixels which satisfies the Pythagorean theorem
There are plenty of line drawing algorithms to discretize line segments using pixels.
The Bresenham's algorithm gives a line where the number of pixels in the segment is the same as its width (in x-...
- 13.2k
10
votes
2
answers
1k
views
Proofs of circle packing theorem
Circle packing theorem is a famous result stating that for every connected simple planar graph $G$ there is a circle packing in the plane whose intersection graph is $G$ https://en.wikipedia.org/wiki/...
- 8,992
2
votes
0
answers
47
views
Source request: Optimal bounds on signings of points from a convex body
I recently came across an old survey of problems in discrete geometry: https://pdfs.semanticscholar.org/c350/f4d4a9466fa6708d99ec1187c63d89bed20f.pdf
Problem 2.1 from the list caught my eye. It states ...
4
votes
0
answers
60
views
How are these "Voronoi-dual" configurations called?
If $\mathscr P\subset \mathbb R^d$ is a discrete point configuration, take the Voronoi diagram of $\mathscr P$ and call $\mathscr P'$ the vertices of that diagram.
I would like to know if ...
- 5,429
3
votes
1
answer
111
views
Reference for "every 5-dimensional polytope has a 3-gonal or 4-gonal face"
It seems to be folklore that every 5-dimensional convex polytope has a 3-gonal or 4-gonal face of dimension two. I was not able to track down a source for that claim.
Alternatively, I would be ...
- 35.5k
2
votes
1
answer
112
views
Reference request: placing a set with respect to the integer grid
For $x=(x_1,...,x_n)\in \mathbb{R}^n$, let $Q_x=(x_1,x_1+1)\times ...\times (x_n,x_n+1)$ - the open cube having $x$ in its "bottom left" corner. It seems, I can prove (see a draft here) the following
...
- 5,529
14
votes
2
answers
878
views
Sets of evenly distributed points in the Euclidean plane
Is there a set $P \subset \mathbb{R}^2$ of points in the Euclidean plane whose intersection
with every convex subset of $\mathbb{R}^2$ of area $1$ is nonempty but finite?
If the answer is yes, can $P$...
- 19k
6
votes
1
answer
295
views
A conjecture (or theorem?) on unit vectors in a Euclidean space
I have heard (if I am not mistaken) that there exists the following conjecture (or theorem?).
Let $u_1,\dots,u_n$ be unit vectors in an $n$-dimensional Euclidean vector space. Then there exists ...
- 10.4k
18
votes
2
answers
840
views
Reference to a conjecture on unit vectors in Euclidean space
I have heard that there exists the following conjecture (if I am not mistaken).
Let $u_1,\dots,u_n$ be unit vectors in an $n$-dimensional Euclidean vector space. Then there exists another unit vector ...
- 763
4
votes
0
answers
230
views
Is this case of Barnette's Conjecture known?
Context: Barnette's Conjecture is that every bipartite cubic polyhedral graph is Hamiltonian. I have been interested by this problem for a long time, and I recently came up with a result. From my ...
- 3,499
1
vote
1
answer
75
views
Given a vertex $u$ (of bounded degree $k$) and another vertex $v$ in a planar graph, what is the smallest number of "curves"?
Given a vertex $u$ (of bounded degree $k$) and another vertex $v$ in a planar graph $G$, what is the smallest number of "curves" in the plane drawn from $u$ to $v$ such that no $u$--$v$ path in $G$ ...
- 32.1k
9
votes
0
answers
100
views
A characterization of root systems via their intersections with halfspaces
In a recent preprint I obtained a nice characterization of root systems as a side product.
I can imagine that this was known before, and that a source for this statement can shorten the proof of my ...
- 13.6k
4
votes
2
answers
173
views
4-polytopes with only one kind of regular facet
Is there a neat way to show (or a reference that already proves) that
the 4-cube is the only convex 4-polytope in which all facets are regular 3-cubes?
the 24-cell is the only convex 4-polytope in ...
7
votes
3
answers
551
views
Minkowski's theorem for non-0-symmetric sets
Let $\Lambda \subseteq \mathbb{R}^n$ be a full-rank lattice, i.e. $\Lambda = A \mathbb{Z}^n$ for some $A \in \mathrm{GL}_n (\mathbb{R})$, and let $C \subseteq \mathbb{R}^n$ be a $0$-symmetric convex ...
- 255
9
votes
1
answer
460
views
Connections between linear representations and permutation representations
A finite group $\Gamma$ might be represented by a linear transformation
$$\rho : \Gamma\to\mathrm{GL}(\Bbb R^d),$$
or by permutations
$$\phi :\Gamma\to\mathrm{Sym}(n).$$
Of course, latter ones can ...
- 11.2k
15
votes
0
answers
477
views
Expanding disks lead to what packing of the plane?
Suppose one sprinkles points uniformly at random on the infinite Euclidean plane,
with some density $\rho$ per unit area.
View the points as disks of radius zero.
Now the radii $r$ of all disks grows ...
- 2,821
2
votes
0
answers
87
views
A theory of (or reference for) symmetric point arrangements
I wonder where I can find something written on symmetric point arrangements (see definition below). I am interested in general references, preferably books that introduce (or papers that use) some ...
- 13.6k
1
vote
1
answer
393
views
Hyperbolic embedding of a directed acyclic graph defined over strings
For integer $n$ and alphabet $\Sigma$ we construct a DAG (directed acyclic graph) $G=(V,E)$ over strings $s\in\Sigma^\star$ as follows:
$$V = \{s\in\Sigma^\star\colon |s|\le n\}$$
$$E = \{(s_1,s_2)\...
- 187
6
votes
4
answers
2k
views
Delaunay triangulations and convex hulls
This is a reference request.
I have the impression that those who work in computational geometry are accustomed to the following. You have some locally finite set of sites in $\mathbb{R}^n$ and you ...
- 151k
3
votes
2
answers
348
views
Request for some references exploring the connections of Riemann surfaces with medical imaging
I'd like to know some references for a beginner who has basic background in Riemann surfaces and differential geometry, and would like to start learning/working on more applied areas, medical imaging/...
4
votes
2
answers
425
views
Algorithm for Reconstructing Point Sites from a Voronoi Diagram
how can one construct a finite set of points in the euclidean plane from its Voronoi Diagram and, what is the complexity of the problem?
- 151k
1
vote
0
answers
69
views
Can sufficiently symmetric polytopes be uniquely reconstructed from their 1-skeleton?
General convex polytopes can not be uniquely reconstructed from their 1-skeleton1, as explained here. Not even the dimension is known from the skeleton, as e.g. the complete graph $K_n,n\ge 5$ is the ...
- 4,713
4
votes
2
answers
349
views
How many dihedral angles need to be specified to uniquely specify a triangulated polyhedron?
Suppose you are given a simplicial complex $K$ homeomorphic to the sphere and for each each edge of the complex a label specifying a length of that edge (this gives us a polyhedral metric on $K$). In ...
- 151k
24
votes
0
answers
760
views
How much of the plane is 4-colorable?
In 1981, Falconer proved that the measurable chromatic number of the plane is at least 5. That is, there are no measurable sets $A_1,A_2,A_3,A_4\subseteq\mathbb{R}^2$, each avoiding unit distances, ...
- 7,633
1
vote
0
answers
278
views
Sphere packings with antipodal (unequal) spheres
Let $\|\cdot\|_2$ denote the Euclidean norm, let $\langle \cdot, \cdot\rangle$ denote the standard dot product, and let $\mathcal{S}^{d-1} = \{\mathbf{x} \in \mathbb{R}^d: \|\mathbf{x}\|_2 = 1\}$ ...
CommunityBot
- 1
17
votes
1
answer
1k
views
The optimal constant in Vitali covering lemma
Let me restate Vitali covering lemma.
Let $\{B_i\}_{i\in F}$ be a finite collection of balls in the $\mathbb{R}^n$. Then there is $S\subset F$ such that the balls $\{B_i\}_{i\in S}$ are disjoint and
...
11
votes
1
answer
607
views
Largest pair of homometric Golomb rulers?
A Golomb ruler is a set of $n$ integers that determines $\binom{n}{2}$ distinct differences.
Two sets are homometric if they determine the same (multiset) of differences.
For example,
$$\{0,1,4,10,12,...
- 2,185
13
votes
1
answer
3k
views
What nets fold to polyhedra?
There is a classic (and open) problem asking whether every polyhedron can be unfolded to give a non-overlapping net. The converse problem has been studied asking which polygons can be folded in some ...
CommunityBot
- 1
13
votes
3
answers
1k
views
Random Reidemeister moves to unknot
Suppose one has a link diagram of the unknot, and applies random Reidemeister moves
until the unknot is reached.
Surely it requires an exponential number of moves, exponential in, say, the crossing ...
- 63.9k
17
votes
5
answers
883
views
Rigidity of convex polyhedrons in $\mathbb R^3$ with faces removed
Take a convex polyhedron $P$ in $\mathbb R^3$ and remove all the faces, i.e. leave only the edges. Call this graph $E$. Let us now try to continuously deform $E$ in $\mathbb R^3$ so that all the edges ...
- 14.3k
11
votes
1
answer
406
views
Thinnest 2-fold coverings of the plane by congruent convex shapes
It is an unsolved problem to determine the "thinnest" $2$-fold covering of
the plane by disks.
The $2$-fold coverage problem by disks is to find the minimum number of congruent
(unit-radius) disks ...
- 151k
21
votes
2
answers
1k
views
On convergence of convex bodies
Let $K\subset \mathbb{R}^n$ be a compact convex set of full dimension. Assume that $0\in \partial K$.
Question 1. Is it true that there exists $\varepsilon_0>0$ such that for any $0<\...
- 7,194
3
votes
1
answer
176
views
Toric Desingularization Algorithms
There are certainly many algorithms to desingularize toric varieties (e.g https://arxiv.org/pdf/math/0411340.pdf). I would imagine in analogy with desingularizing surfaces these all involve blowing up ...
- 1,595
45
votes
1
answer
2k
views
Pach's "Animals": What if the genus is positive?
Janos Pach asked a deep question 23 years ago (1988) that remains unsolved today:
Can every animal—a topological ball in $\mathbb{R^3}$ composed of unit cubes glued face-to-face—be ...
- 151k
7
votes
3
answers
805
views
Wrapping a convex polyhedron with string
This is a meta-question, rather than a specific mathematical question.
I am seeking a mathematical definition that captures the following physical idea.
Suppose you have a convex polyhedron $P \...
- 18.6k
16
votes
6
answers
2k
views
Optimal pebble-packing shape
Suppose you throw many ($n$) congruent convex bodies (in $\mathbb{R}^3$) of unit volume (or of unit area in $\mathbb{R}^2$) into a large container, and shake it until little else changes.
Q. ...
- 151k
14
votes
1
answer
819
views
The geometry of crinkled aluminum foil
I wonder if the geometry of crinkled aluminum foil has been studied?
The above is a photo of foil I flattened to reuse.
It might be ...
- 151k
17
votes
1
answer
458
views
The sparsest planar net that captures every unit segment
Let $\cal C = \lbrace C_i \rbrace$ be a collection
of rectifiable curves in the plane with the property that
every unit-length segment meets at least one curve
in at least one point.
Call such a ...
- 151k
14
votes
1
answer
781
views
Perimeters of random-walk polygons
I have a random walk on $\mathbb{Z}^2$ that takes a step
with equal probability in the three directions that avoid
retracing the previous step.
The walk proceeds until it returns to a lattice point
...
- 151k
8
votes
1
answer
885
views
Maximal tetrahedra inscribed in ellipsoid
Pietro Majer quoted the theorem of Michel Chasles in his MO question,
"Convex curves with many inscribed triangles maximizing perimeter,"
which states that the triangles of maximum perimeter inscribed ...
- 151k
4
votes
0
answers
153
views
Perimeters of nested convex spherical polygons
I seek a reference—not a proof—that if $P_1$ and $P_2$
are two convex polygons on a sphere composed of geodesic segments,
contained in a hemisphere, and
$P_1 \subseteq P_2$, then the ...
- 151k
3
votes
1
answer
394
views
Min Bend Orthogonal Knots
I am seeking literature on 3D orthogonal drawings of knots,
especially minimum bend drawings.
An orthogonal drawing employs segments parallel to the axes of
a Cartesian coordinate system.
A bend is a ...
CommunityBot
- 1
1
vote
0
answers
371
views
Simple development of simple curve on a cone
Let $\Lambda$ be a cone with apex $a$ and apex angle $\alpha$. Draw a simple (non-self-intersecting)
curve $C=(x,y)$ on $\Lambda$, and then develop it to a curve
$\overline{C}$ on a plane by rolling $...
- 151k
4
votes
1
answer
323
views
What properties does generalized Delaunay triangulation have?
Suppose that instead of the usual circle, we pick some other convex set D and make the Delaunay triangulation of a finite planar point set with respect to this set, i.e. connect two points if there is ...
- 4,713
13
votes
2
answers
1k
views
Average degree of contact graph for balls in a box
Imagine you dump congruent, hard, frictionless balls in a box,
letting gravity compress the balls into a stable configuration
(I believe such configurations are called
jammed.)
Assume the box ...
- 13.6k
10
votes
2
answers
280
views
Monochromatic point sets in two-colored plane
Which are the configrations $P\subset \mathbb{R}^2$ of points, such that the following property holds:
Property M (for Monochromatic): Every two-coloring of $\mathbb{R}^2$ contains a monochromatic ...
- 151k
6
votes
2
answers
364
views
Triangles whose vertices and center have all the same color
A plane is colored with two colors. It's an easy exercise to prove that it's always possible to find an equilateral triangle whose vertices have all the same color.
Does anyone know any proof or ...
CommunityBot
- 1