Questions tagged [triangulations]
The triangulations tag has no usage guidance.
129 questions
5
votes
1
answer
453
views
Every manifold can be cut into cubes
I saw the following statement in my advanced calculus text, which was presented without proof:
If $\bar{D}$ is a compact domain in the plane (that is, closure of an open, connected and bounded subset ...
- 151
0
votes
0
answers
98
views
Number of tetrahedra inside a sphere with boundary A
I understand, that there are some combinatorial problems which are not yet solved regarding gluing triangulations in 3D. At least last time I checked, it was not yet known exactly how many ...
- 183
5
votes
2
answers
222
views
$\mathbb{CP}(2)$ from gluing boundary of 4-ball
Many manifolds can be obtained from gluing the boundary of a ball. For example, $\mathbb{RP}(2)$ is obtained from gluing the two edges of a bi-gon (2-ball). Or, lens spaces are obtained from a 3-cell ...
- 3,001
9
votes
0
answers
212
views
Left adjoint functor between categories of polygons?
EDIT: Based on very helpful comments from Alec Rhea and Qiaochu Yuan I am adding some specification on objects and morphisms, hoping that this clarifies the idea behind these categories. I have also ...
- 6,937
1
vote
0
answers
22
views
Calculating an optimal scaling factor for Delaunay triangulations
consider a finite set $\mathcal{P}(x,y)=\lbrace(x_1,y_1),\dots,\,(x_n,y_n)\rbrace$ of points in the Euclidean plane and let $\mathrm{DT}(x,y)$ be the Delaunay triangulation of $\mathcal{P}(x,y)$
...
- 13.2k
6
votes
2
answers
404
views
Estimating shortest paths in planar drawings of graphs
Consider a drawing (in $\mathbb{R}^2$) of a planar graph. (The drawing is given, contrarily to the common setup in graph theory where we are seeking to build a drawing with specific properties.)
For ...
- 307
5
votes
1
answer
380
views
existence of triangulations of manifolds
Let $M$ be a smooth manifold.
Let $K$ be a simplicial complex.
Let ${\rm sd}(K)$ be the sub-division of $K$.
Suppose there exists a simplicial sub-complex $K_1$ of ${\rm sd}(K)$ such that $K_1$ ...
- 123
9
votes
0
answers
186
views
What is an intuitive explanation for a manifold to have no triangulation?
It is known that some topological manifolds, even compact and simply-connected ones, do not have admit a triangulation. One example is the E8 manifold in a dimension as low as $4$.
I am trying to ...
- 5,327
5
votes
0
answers
190
views
Triangulating piecewise-linear manifolds
Question 1: Is this the mainstream definition of a PL-manifold?
Definition. A PL-manifold is a manifold with an atlas $(\varphi_i)_{i\in I}$ in which all transition maps $\varphi_j\circ\varphi_i^{-1}$ ...
- 396
3
votes
0
answers
69
views
Volume of all Voronoi cells in n-dimensional bounded space
How can one find the volume of all Voronoi cells (bounded and unbounded) in an $n$-dimensional bounded space? For instance, consider an $N$-dimensional space (hypercube) with bounds on each dimension ...
- 131
0
votes
0
answers
125
views
Naming convention for different type of triangulations
When studying random geometries and related mathematical/physical stuff conflicting naming convention pops up regarding the naming of the different ensemble types of triangulations (in general ...
- 183
1
vote
0
answers
84
views
Number of polyhedral covers of a triangulation of $S^2$
For a given triangulation (combinatorial Type I. or Type II.) of a $2$-sphere, what is the number of unique polygonal covers with $n$ polygons where ($n$ goes from $2$ to $N$)?
Under polygonal cover, ...
- 183
9
votes
4
answers
475
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 ...
- 479
3
votes
0
answers
93
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-...
- 183
1
vote
0
answers
137
views
References/applications/context for certain polytopes
First, let's consider an almost trivial notion. With any subspace $V\subset \mathbb R^n$ we associate a convex polytope $P(V)\subset V^*$ as follows. Each of the $n$ coordinates in $\mathbb R^n$ is a ...
- 3,513
5
votes
1
answer
119
views
Sufficient condition for a Hamilton cycle $C$ in a planar triangulation $G$ s.t. every triangle in $G$ has an edge in $C$
Let $G$ be a $k$-connected planar triangulation ($k\geq 4$) and let $C$ be a Hamilton cycle of $G$. Then:
Which conditions would be sufficient to assure that every triangle of $G$ has at least one ...
8
votes
3
answers
921
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+...
- 509
2
votes
1
answer
92
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 ...
- 13.2k
8
votes
2
answers
849
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 ...
- 183
1
vote
1
answer
97
views
Is every triangulation the projection of a convex hull
Question:
given the triangulation $T$ of a set $P$ of $n$ points $p_1,\dots,p_n$ in the euclidean plane whose convex hull is a triangle, can we always find a set $Q$ of $n+1$ points $q_0,q_1,\dots,q_n$...
- 13.2k
1
vote
1
answer
73
views
Partitioning polygons into obtuse isosceles triangles
Ref:
Partitioning polygons into acute isosceles triangles
Partition of polygons into 'strongly acute' and 'strongly obtuse' triangles
https://math.stackexchange.com/questions/1052063/...
- 5,979
1
vote
0
answers
132
views
What is the difference between a simple polyhedron and a triangulated graph?
On a famous website I've seen the following:
The skeletons of the simple polyhedra correspond to the triangulated graphs, the smallest of which are illustrated above. That "illustration above&...
- 11
2
votes
1
answer
138
views
Two ears polygon in a maximal planar hamiltonian graph
Given a maximal planar graph (+6vertices) without separating triangles. Then it can have many Hamilton cycles°. Such a cycle divides the graph into two triangulated polygons. Is it always possible to ...
- 35
6
votes
2
answers
370
views
Does every triangulable manifold have a vertex-transitive triangulation?
Does every triangulable manifold have a vertex-transitive triangulation?
When I talk about a vertex-transitive triangulation of a manifold, I mean in the sense of realizing a manifold homeomorphically ...
- 345
3
votes
1
answer
255
views
Handle attachment information from Morse function and triangulation
First, allow me to setup the relevant information. It is well known that a Morse function $f:M\to\mathbb{R}$ induces a handle decomposition of $M$.
For simplicity, let's restrict for now to the ...
- 159
5
votes
1
answer
223
views
Proof of Lemma 37.5 in Pak's Lectures on Discrete and Polyhedral Geometry
I am staring at the proof of Lemma 37.5 in Lectures on Discrete and Polyhedral Geometry, see page 331.
I cannot understand why the required triangulation exists.
In the first paragraph it says "...
- 14.3k
1
vote
1
answer
179
views
Relation of MSTs in the Euclidean plane to Delaunay triangulations
It is known that the Minimum Spanning Tree (MST) of a finite set of points in the Euclidean plane is contained in the point set's Delaunay triangulation, but is that all that can be said about their ...
- 13.2k
5
votes
3
answers
245
views
Ideal triangulations of $3$-manifolds with "cusps" of genus $\ge 2$
Typically when one thinks about ideal triangulations of a $3$-manifold the link of each ideal vertex is a circle, so the ideal points correspond to toroidal cusps; alternatively, one can truncate the ...
- 2,533
1
vote
0
answers
62
views
What are some other methods for partitioning an n-dimensional space based on a set of points in that space?
So this is a very general question, but I'm curious if there are any other methods for partitioning an n-dimensional space based on the location of a set of points, either randomly chosen or specified,...
- 11
0
votes
1
answer
518
views
Distance between two points using triangulation
Suppose we have two points $p_1$ and $p_2$ in a metric space with unknown dimensionality, with no way to directly compute the distance between them, e.g. no coordinates.
Say we can randomly sample a ...
0
votes
1
answer
101
views
A question on relation of different triangulations of a triangulable space
Suppose we get two triangulations of a manifold with boundary $M$ such that the triangulation is compatible with boundary, i.e. the restriction on the boundary is itself a triangulation, is it these ...
- 781
4
votes
1
answer
304
views
Do combinatorially equivalent polytopes have the same triangulations?
A triangulation of a convex polytope $P\subset\Bbb R^n$ is a partition of $P$ into $n$-simplices $\{\Delta_1,...,\Delta_m\}$ each of which has all its vertices among the vertices of $P$. A polytope ...
- 13.6k
1
vote
1
answer
135
views
Annulus theorem for pseudomanifolds
Lets say I take an arbitrary closed and smooth $d$-manifolds $\mathcal{M}$. Now, it is a well-known fact that whenever I take two (sufficiently nice embedded) closed $d$-balls $B_{1}$ and $B_{2}$ in $\...
- 1,429
1
vote
0
answers
259
views
How to do an elevated 2D Delaunay triangulation?
This is what I call an elevated Delaunay triangulation:
This is also called a 2.5D Delaunay triangulation.
To do it, I simply perform an ordinary 2D Delaunay triangulation with the (x,y)-coordinates, ...
- 2,560
9
votes
1
answer
484
views
Refining a triangulation
I'm reading Thurston's article "Shapes of polyhedra and triangulations of the sphere." In the introduction he claims the following:
"${}^{(1)}$There are procedures to refine and modify ...
- 395
4
votes
1
answer
255
views
Is every (not necessarily PL-) triangulation of a manifold pure, non-branching and strongly-connected?
A triangulation of a topological manifold $\mathcal{M}$ possibly with boundary is an abstract simplicial complex $\Delta$ together with a homeomorphism $\varphi:\vert\Delta\vert\to\mathcal{M}$, where $...
- 1,171
2
votes
0
answers
75
views
Triangulations with discrete metrics and conformal equivalence
A discrete metric for a triangulation of a 2-dimensional manifold is a map associating $\mathbb{R}_+$-valued lengths to all edges, such that the triangle inequality holds on every triangle. In many ...
- 3,001
1
vote
0
answers
49
views
Influence of the degenerate Delaunay tiles on the Voronoï diagram
About three or four years ago, I implemented the Delaunay and Voronoi tessellations in Haskell, with the help of the Qhull C library. Now I reimplement it in R.
I have noticed that including or not ...
- 2,560
7
votes
1
answer
260
views
Bordism for oriented triangulable manifolds without smooth differentiable structures
We know the bordism group for oriented smooth differentiable structures such as $\Omega_d^{SO}$ that requires the special orthogonal group structure on the tangent bundle $TM$ of manifold $M$.
$$\...
- 10.5k
12
votes
0
answers
229
views
3-manifolds with stacked links
Stacked spheres
A triangulation of a 2-dimensional sphere is called a stacked sphere if it is obtained inductively from the boundary of a 3-simplex by deleting a 2-face (triangle) $T$ adding a new ...
- 24.7k
8
votes
2
answers
630
views
Presentations of exotic 4-manifolds
TLDR I want to see more examples of exotic $4$-manifold (hopefully connected, simply connected, oriented, and closed).
Are there known presentations of $4$-manifolds $M$ with exotic structures, ...
- 5,230
4
votes
1
answer
418
views
Triangulation of a simplex
I am looking for a triangulation of an $n$-dimensional simplex such that all sub-simplices are of comparable size, and are "as close as possible" to a regular simplex : the latter property ...
- 43
2
votes
0
answers
60
views
Relation between symmetries of hyperbolic knot and the symmetries of a generic triangulation
For canonical ideal triangulation of a hyperbolic knot, the symmetries of the knot are the same as the symmetries of that triangulation. This is how SnapPy computes the knot symmetry group.
Is there ...
- 63
4
votes
1
answer
196
views
Ideal triangulation of hyperbolic 3-manifold with generic mapping class group
I am from physics background so I apologize in advance if my question is trivial.
Kojima proves for every finite group $G$, there is a hyperbolic 3-manifold such that its mapping class group equals $G$...
- 63
6
votes
0
answers
123
views
Hamiltonicity for triangulations of the 3-sphere
A classical theorem of Whitney states that the 1-skeleton of every triangulation of the 2-sphere $\mathbb{S}^2$ has a Hamilton cycle as long as each of its 3-cycles bounds a triangle.
I'm wondering if ...
- 1,936
9
votes
1
answer
793
views
Properties a triangulation must have in order to describe a manifold
I am mainly interested in the $3$-dimensional case. It is a well-known fact, following from the work of E. E. Moise and R. H. Bing in the 1950s, that every $3$-dimensional topological manifold (with ...
- 1,429
8
votes
1
answer
618
views
When is a triangulation of sphere two-colorable?
Let $T$ be a triangulation of sphere. We say that $T$ is $k$-colorable if the triangles of $T$ can be assigned with $k$ colors such that any two triangles with a common edge have different colors.
I ...
- 30.6k
1
vote
1
answer
51
views
On triangulations and "coverage" of circumcircles
Let $P$ be a convex quadrilateral defined by four vertices $a$, $b$, $c$, and $d$. Suppose that the circumcircle of $\triangle abd$ contains $c$.* Let $D(\triangle abc)$ to denote the area enclosed by ...
- 173
1
vote
0
answers
87
views
refining a coherent triangulation
I am relatively new to this topic, so this question may be easy/naive to some experts. Here goes..
I have a finite set of points $S\subset\mathbb R^2$ (you may increase the dimension of the ambient ...
- 2,275
5
votes
0
answers
214
views
Covering the sphere with an approximately planar grid
Consider a triangulation of a radius $R$ sphere into $n$ triangles. Must $Ω(\sqrt n)$ triangles have $Ω(1)$ relative difference from being an equilateral triangle of area $4πR^2/n$? ($Ω$ is from ...
- 7,545