Questions tagged [triangulations]
The triangulations tag has no usage guidance.
121
questions
4
votes
0
answers
120
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}$ ...
- 346
3
votes
0
answers
49
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
122
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 ...
- 75
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, ...
- 75
9
votes
4
answers
413
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 ...
- 469
3
votes
0
answers
90
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-...
- 75
1
vote
0
answers
136
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,493
5
votes
1
answer
106
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
803
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+...
- 449
2
votes
1
answer
76
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 ...
- 12.7k
8
votes
2
answers
755
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 ...
- 75
1
vote
1
answer
83
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$...
- 12.7k
1
vote
1
answer
69
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,493
1
vote
0
answers
114
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
128
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
5
votes
2
answers
338
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 ...
- 335
3
votes
1
answer
220
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
215
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 "...
- 14k
1
vote
1
answer
165
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 ...
- 12.7k
5
votes
3
answers
227
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,483
1
vote
0
answers
50
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
404
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
89
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 ...
- 771
4
votes
1
answer
284
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 ...
- 12.6k
1
vote
1
answer
100
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,147
1
vote
0
answers
176
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,433
9
votes
1
answer
445
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
3
votes
1
answer
202
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 $...
- 987
2
votes
0
answers
69
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 ...
- 2,901
1
vote
0
answers
46
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,433
7
votes
1
answer
248
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.3k
12
votes
0
answers
222
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.2k
8
votes
2
answers
546
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,038
4
votes
1
answer
371
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
165
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
121
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,854
6
votes
1
answer
554
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,147
8
votes
1
answer
594
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.3k
1
vote
1
answer
50
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
77
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,175
5
votes
0
answers
202
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 ...
- 6,112
15
votes
1
answer
605
views
Acute triangles in "obtuse" polygons?
Let $P$ be a convex polygon. Suppose every interior angle of $P$ is obtuse. Is it always the case that there exist three vertices $p, q, r$ of $P$ such that $\triangle pqr$ is acute?
I conjecture ...
- 173
6
votes
0
answers
162
views
Can $X_4 \times S^1$, $X_4 \times I^1$, or $X_4 \times \mathbb{R}^1$ be a triangulable, PL or DIFF manifold, if $X_4$ is a non-triangulable manifold? [duplicate]
Question: If $X_4$ is a non-triangulable topological (TOP) manifold,
can $X_4 \times S^1$, $X_4 \times I^1$, or $X_4 \times \mathbb{R}^1$ be a triangulable manifold?
can $X_4 \times S^1$, $X_4 \...
- 10.3k
6
votes
0
answers
208
views
If $X_d$ is a non-triangulable manifold, can $X_d \times T^k$, $X_d \times I^k$, or $X_d \times \mathbb{R}^k$ be a triangulable manifold?
If $X_d$ is a non-triangulable manifold, can $X_d \times T^k$, $X_d \times I^k$, or $X_d \times \mathbb{R}^k$ always be a triangulable manifold?
Let $X_d$ be a $d$-manifold which is NOT a ...
- 10.3k
3
votes
1
answer
121
views
Surfaces generated by minimum-weight triangulations
The minimum-weight triangulation of simple polygons can be efficiently calculated in $O(n^3)$ time by dynamic programming, while it is $\text{NP-hard}$ for pointsets in general.
Looking at the ...
- 12.7k
4
votes
0
answers
101
views
Retriangulating manifolds via triangulations of low local complexity
Suppose that $M$ is closed, connected PL $n$-manifold. We say that a triangulation of $M$ has local complexity at most $L$ if every zero-cell of $T$ meets at most $L$ $n$-simplices. (An alternative ...
- 26.4k
2
votes
0
answers
23
views
What is known about $\operatorname{card}_E(\mathrm{MST}\cap\mathrm{MWT})$?
It is a wellknown fact of computational geometry that the edges of Minimum-weight Spanning Tree are also found in the Delaunay Triangulation of a planar pointset $\mathcal{P}$, i.e. $\operatorname{...
- 12.7k
14
votes
0
answers
381
views
Minimum number of distinct triangles for tesselating the sphere
Consider sequences of tesselations of the sphere. For instance, one such sequence might start with an icosahedron and proceed by subdividing each triangle face into 4 triangles and projecting the new ...
- 1,892
8
votes
0
answers
163
views
Is there a combinatorial representation of general topological manifolds similar to triangulations?
Piece-wise linear manifolds are combinatorially represented by simplicial complexes modulo Pachner moves. However, for dimensions greater than $3$, the notions of piece-wise linear and topological ...
- 2,901