All Questions
Tagged with discrete-geometry reference-request
174 questions
4
votes
2
answers
207
views
Classification of symmetries of tilings in surfaces?
Is there a general study of the symmetries of tilings on surfaces?
Conway, Goodman-Strauss & Burgiel classified them on $\mathbb S^2, \mathbb R^2$ and $\mathbb H^2$, with their 'Magic Theorem'. ...
- 561
4
votes
2
answers
506
views
Empty lattice simplex or White's theorem
White has proved (White, G. K. Lattice tetrahedra -- Canad. J. Math. 16 1964 389–396.) the following theorem:
If $T$ is a closed tetrahedron and $\Lambda$ is a lattice which contains the vertices of $...
- 12.3k
4
votes
1
answer
282
views
A combinatorial problem about sequences of numbers
In this math.stackexchange question Adam Rubinson asked (I paraphrase):
Given a natural number $r$, what is the least number $n$ such that every strictly increasing sequence of $n$ real numbers has a ...
- 13.4k
4
votes
0
answers
234
views
To whom is the classification of atomic, modular finite lattices due?
Here lattice means a poset with meets and joins. A lattice is called atomic if every element is a join of atoms. There are a few different ways to define modular for finite lattices: one is that the ...
- 24.2k
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 ...
- 2,041
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
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
4
votes
0
answers
213
views
Counting the polytopes of the translates of the resonance hyperplane arrangement inside the unit hypercube
Let $n$ be a positive natural number. For all $\emptyset \subset S \subseteq \{1, \ldots, n\}$ and $k \in \mathbb{Z}$, define the hyperplane $H(S,k)$ in $\mathbb{R}^n$ given by the equations
$$H(S,k):=...
- 283
4
votes
0
answers
164
views
Two variants of the Littlewood-Offord theorem
I found two different looking things being called the Littlewood-Offord theorem,
If $\vec{a} \in \mathbb{R}^k \setminus 0$ and $t \in \mathbb{R}$ then there are $O(\frac{2^k}{\sqrt{k}})$ points $x \...
- 2,246
4
votes
0
answers
143
views
Balanced partitions of vector sets
We are interested in the following
Lemma. Let $V\subset [0,1]^n\subset\mathbb R^n$ be a set of $n$-dimensional vectors. Then for each $r\le |V|$ there exists a partition $$V=V_1\cup V_2\cup\dots \cup ...
- 5,409
4
votes
0
answers
158
views
Reference for the notion of polyhedra "degenerations"
Let $P$ be a convex polyhedron and let $P(t)$ be a continuous deformation thereof, such that:
a) $P(0)=P$;
b) for all $t\in[0;1)$ the polyhedron $P(t)$ is strongly combinatorially equivalent to $P$ (...
- 3,513
4
votes
0
answers
189
views
Slices of Simplices that are Simplices, Reference?
I am trying to find a reference for the following fact. It is elementary and not hard to prove, but I haven't been able to find the question treated anywhere.
Let $A$ be an $l\times n$ matrix with ...
- 41
3
votes
3
answers
330
views
Voronoi and Delaunay
Please provide some references on Voronoi and Delaunay decompositions which is mathematically written. I mean I can find several texts or links on this written for computer science students without ...
user111251
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 ...
- 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/...
- 1,467
3
votes
1
answer
1k
views
Regularity of Delaunay triangulation of a hypercube
First using a three dimensional unit cube as an example for the term "regularity", we can have two possible triangulations:
(A)
(B)
We say the lower triangulation is more "regular" than upper ...
- 339
3
votes
1
answer
108
views
Has this random process been studied on grid graphs?
As an offshoot of a different discussion I got curious about (uniform) random spanning trees on grid graphs (torus graphs in particular, to avoid having to think about edge effects) and what their ...
- 1,951
3
votes
1
answer
159
views
Work on "Churning Polygons"
Background of this question is that I recently stumbled over the problem of deforming polygons in area-preserving way, i.e. modifying the angles between adjacent edges while preserving edge-lengths, ...
- 13.2k
3
votes
1
answer
191
views
Maximal $\pi/2$-separated subset of the sphere
A subset $A$ of a metric space is called $\varepsilon$-separated if
$$dist(x,y)> \varepsilon \mbox{ for all } x\ne y\in A.$$
(Notice that the inequality in my definition is strict.)
What is the ...
- 21.8k
3
votes
1
answer
853
views
Transience of self avoiding random walks on $\mathbb{Z}^d$
I'm finishing up a masters thesis in computer science and want to say a bit in the introduction about self-avoiding walks. My thesis looks at a random process which arose in computer science and my ...
- 30.3k
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 ...
- 13.6k
3
votes
2
answers
261
views
Examples of toric threefolds
I am looking for examples of smooth projective toric threefolds $\mathbb P_\Delta$ such that the rational polytope $\Delta$ has only pentagonal faces and hexagonal faces.
I quickly searched for ...
- 441
3
votes
1
answer
356
views
Empty convex polytopes for random point sets
I know of the famous results on the Erdős-Szekeres empty convex polygon problem in the plane
(the Happy-Ending Problem), and I know that there are higher-dimensional extensions.
A great source (...
- 151k
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....
- 45
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 ...
- 528
3
votes
1
answer
292
views
Existence of Simple Closed Straightest Geodesics
There are at least three distinct simple closed quasigeodesics on convex polyhedra [Mat. Sb. (N.S.), 1949, 25(67) :2, 275–306 Quasi-geodesic lines on a convex surface Pogorelov].
Is the same true ...
- 133
3
votes
0
answers
208
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 ...
- 27.7k
3
votes
0
answers
93
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 ...
- 12.3k
3
votes
0
answers
116
views
A theory of refined h- and f-polynomials for the permutahedra, associahedra, noncrossing partitions, and tropical Grassmannians (references)
Looking for references (insights) on a theory encompassing a notion of refined face polynomials and their associated refined h-polynomials that are generalizations of the relation between ordinary f-...
- 10.5k
3
votes
0
answers
234
views
Do you know this formula for the scalar product in barycentric coordinates?
I've found a formula for a scalar product in barycentric coordinates which I think is pretty cool. I hope that it's new. Is it?
Suppose that you have points $x_1,\dots,x_n$ sitting in general position ...
- 1,058
3
votes
0
answers
86
views
Sums over lattice points in homogeneously expanding domains
In his book Algebraic Number Theory (2nd ed., Thm 2 in p.128), Lang proves the following (well-known) auxiliary result. Let $D\subset\mathbb{R}^N$ with $(N-1)$-Lipschitz parametrizable boundary. Let $...
- 3,107
3
votes
0
answers
135
views
Intersecting the unit n-cube and (n-1)-planes
(Is this a known problem?)
Question Let $\ 1<n\in\mathbb N.\ $ What is the greatest $(n-1)$-area
$\ S(n)\ $ of $\ L\cap I^n\ $ where $\ I^n\subseteq\mathbb R^n\ $ is the unit cube, and $\ L\ $ ...
- 4,786
3
votes
0
answers
144
views
Counting homologically non-trivial and trivial cycles in $n \times n$ square lattice torus of a given length $l \geq n$
This should be a fairly standard question but I can't really seem to find a reference.
Consider an $n \times n$ square lattice torus $\mathbb T$. Given a length $l \geq n$, what is the number of ...
- 269
3
votes
0
answers
169
views
Computing Voronoi poles in $\mathbb{R}^d$ (the farthest points within each cell)
Say I have a Voronoi diagram of some points $p_1,\dots,p_n\in\mathbb{R}^d$, which tesselates $\mathbb{R}^d$ into cells $V_1,\dots,V_n$. Within each cell $V_i$, the pole is defined as the vertex of $...
- 41
3
votes
0
answers
391
views
Dissection of a polygon into convex polygons
Problem: for a fixed integer $m\geqslant 3$ find all $n$ such that no $n$-gon can be dissected into convex $m$-gons.
I would be very grateful for any information on this problem.
Remark 1. There ...
- 935
3
votes
0
answers
142
views
Dimension of convex arrangements for hypergraphs
Suppose you have a hypergraph H on n vertices. Let d be the smallest integer such that we can find an arrangement A of convex subsets in Rd so that H represent the intersections of sets in A.
Has ...
- 4,586
2
votes
1
answer
242
views
Smallest angle among two lines in an n × n grid
Does anybody have a reference answering the following (at least for me surprisingly non trivial) question?
Given an $n \times n$ integer grid, what is the minimum angle between any two distinct lines,...
- 239
2
votes
2
answers
284
views
Three questions concerning lattice points on sphere surfaces
Pardon my ignorance of this topic.
Q1.
In which dimensions $d$ is it the case that, for every natural number $n$,
there exists a sphere having exactly $n$ lattice points on it $(d{-}1)$-...
- 151k
2
votes
1
answer
143
views
Triangles and convex hulls in high dimensions
Given a set $S_n$ of $n$ points $\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n\in\mathbb{R}^d$, such that every $(d+1)$-tuple in $S_n$ is affinely independent, and let $C(S_n)$ be the convex hull ...
- 1,677
2
votes
1
answer
106
views
Are zonotopes determined by their edge-graph?
General polytopes are not determined by their edge-graph (up to combinatorial equivalence). But I came accross the statement that zonotopes are determined in this way.
Question: Is this true? And ...
- 13.6k
2
votes
2
answers
163
views
References for geometric properties of optimal Euclidean traveling salesman tour
Consider a finite set of points $V \subseteq \mathbb{R}^2 $ as a TSP-instance under the standard $\| \cdot \|_2$ norm. (TSP stands for traveling salesman tour.) We know that every optimal TSP tour $T$ ...
- 29
2
votes
2
answers
164
views
Angle between a point in a convex polytope and the nearest point of a face
Let $P \subset \mathbb{R}^d$ be a convex polytope, and let $F$ be a face of $P$ (of co-dimension 1, let's say). Now let $x \in P \setminus F$ and let $y \in F$ be the nearest point of $F$ to $x$. Then ...
- 153
2
votes
1
answer
157
views
Bound for a sequence of vertices in a graph
I have come across the following problem. Let $d\in\mathbb{N}$. Let $G$ be any $k$-regular connected directed graph with $n$ vertices, no parallel edges and no 2-cycles. For a vertex $v\in G$, let $...
- 167
2
votes
1
answer
127
views
The density of a tripartite 1-planar graph
1-planar graphs are those can be drawn in the plane so that there is at most one crossing per edge. We know that the maximum number of edges of an $n$-vertex 1-planar graph is at most $4n-8$, and the ...
- 1,190
2
votes
2
answers
676
views
Midpoint lattice polygons
Midpoint polygons (a.k.a Kasner polygons) have been studied, and their behavior is well understood.
I am considering a variant, which I call midpoint lattice polygons.
Start with a sequence of ...
- 151k
2
votes
0
answers
65
views
Structure Theory for Tree Decompositions
I that $G=(V,E,W)$ is a weighted graph with positive edge weights and a finite set of vertices $K$. Let $0\le k,M\le K$ be a fixed integer.
Is is known when $G$ admits the following type of ...
- 21
2
votes
0
answers
77
views
Flexagons and noncrossing partitions
Turns out a couple of series related to the faces of flexagons
popped up in my explorations of combinatorial reciprocities in a group algebra for sets of partition polynomial (ParPs) related to the ...
- 10.5k
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 ...
