# Questions tagged [triangulations]

The triangulations tag has no usage guidance.

109
questions

0
votes

0
answers

17
views

### Approximation of connected set by triangluation / covering by simplices

Good afternoon. I have two distinct questions:
If I have connected compact in $\mathbb{R}^n$, how much $(n+1)$-simplices are needed to fill its interior such that diameter of maximal uncovered part ...

1
vote

0
answers

90
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&...

2
votes

1
answer

123
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 ...

5
votes

2
answers

286
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 ...

3
votes

1
answer

146
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 ...

5
votes

1
answer

183
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 "...

1
vote

1
answer

67
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 ...

5
votes

3
answers

185
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 ...

1
vote

0
answers

34
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,...

0
votes

1
answer

177
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

83
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 ...

4
votes

1
answer

232
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 ...

1
vote

1
answer

76
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
vote

0
answers

54
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, ...

9
votes

1
answer

404
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 ...

3
votes

1
answer

157
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 $...

2
votes

0
answers

51
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 ...

1
vote

0
answers

39
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 ...

1
vote

0
answers

102
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$.
$$\...

12
votes

0
answers

210
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 ...

5
votes

1
answer

368
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, ...

4
votes

1
answer

303
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 ...

1
vote

0
answers

52
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 ...

4
votes

1
answer

126
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$...

6
votes

0
answers

109
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 ...

6
votes

1
answer

406
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 ...

8
votes

1
answer

567
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 ...

1
vote

1
answer

45
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 ...

1
vote

0
answers

65
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 ...

5
votes

0
answers

178
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 ...

15
votes

1
answer

584
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 ...

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 \...

6
votes

0
answers

204
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 ...

3
votes

1
answer

85
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 ...

4
votes

0
answers

92
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 ...

2
votes

0
answers

22
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{...

14
votes

0
answers

335
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 ...

8
votes

0
answers

160
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 ...

9
votes

1
answer

392
views

### Local behavior of smooth triangulations

If $M$ is a smooth $n$- manifold, a smooth triangulation is defined to be a homeomorphism from a simplicial complex $K$ to $M$ whose restriction to each simplex is a smooth embedding. It's a well-...

12
votes

3
answers

780
views

### Can triangulations (or some related combinatorial structure) distinguish smooth structures on $RP^4$?

There are exotic versions of $RP^4$, constructed by Cappell-Shaneson, which are homeomorphic but not diffeomorphic to the standard $RP^4$. One way to distinguish them is via the $\eta$ invariant of $...

0
votes

0
answers

30
views

### Restrictions on crossing edges in Delaunay triangulations

what can be said about crossing edges in Delaunay triangulations, i.e. about pairs of edges that constitute to the heaviest perfect matching int the $K_4$ induced by the quadruplet of adjacent ...

8
votes

0
answers

181
views

### Are triangulations of n-dimensional manifolds determined by lower-dimensional skeleta?

Suppose that $M$ is an $n$-dimensional manifold equipped with a triangulation $T$. Given $n\ge 1$, in order to recover $T$ (up to an isomorphism of simplicial complexes) one needs to know at least ...

1
vote

0
answers

119
views

### Regular triangulation of hypercube

I have started studying regular subdivisions of the $n$-cube, and came across the following post: Regularity of Delaunay triangulation of a hypercube.
My question is whether the "standard ...

3
votes

1
answer

88
views

### Uniqueness constraints for Delaunay triangulation

Commonly the assumption that is made on point sets that shall be Delaunay-triangulated is that no three are collinear and no four are cocircular.
Those assumptions are however too restrictive: if ...

10
votes

2
answers

718
views

### On Gromov's proof of the systolic inequality $\operatorname{Sys}_1(M)\leq 6\operatorname{FillRad}(M)$

In the page 10 of the paper "Filling Riemannian manifolds" by Gromov (ProjetEuclid link), the author proves the following inequality (1.2) relating the systole and the filling radius of manifolds.
$$\...

2
votes

0
answers

47
views

### Triangulations of conformal manifolds

I'm seeking for a discrete representation of $2$-manifolds with a conformal structure (i.e. metric modulo scalar prefactor).
The topology of a $2$-manifold is determined by the combinatorics of a ...

4
votes

0
answers

150
views

### (Non-)Orientability of non-triangulable manifolds

We heard and learned from Mike Miller's answer to Not all manifolds can be triangulated: In which dimensions? that "All orientable 5-dimensional manifolds are triangulable. In dimensions at least ...

4
votes

1
answer

1k
views

### On Thurston's triangulations of sphere

I have two questions from Thurston's paper [1].
In the paper [1], Thurston talks about classifying certain classes of triangulations of the sphere. Here a triangulation of a sphere a Topological ...

3
votes

0
answers

196
views

### Category of Manifolds and Maps: TOP $\supseteq$ TRI $\supseteq$ PL $\supseteq$ DIFF? [closed]

Please let me denote the following
(TOP) topological manifolds https://en.wikipedia.org/wiki/Topological_manifold
(PDIFF), for piecewise differentiable https://en.wikipedia.org/wiki/PDIFF
(PL) ...

6
votes

1
answer

407
views

### Are triangulations of compact manifolds PL homeomorphic?

I have frequently come across the statement "Any two triangulations of a compact n-manifold are related by bistellar moves" attributed to Pachner via Lickorish's paper 'Simplicial moves on complexes ...