# Questions tagged [triangulations]

The triangulations tag has no usage guidance.

124
questions

6
votes

2
answers

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

5
votes

1
answer

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

9
votes

0
answers

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

4
votes

0
answers

136
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}$ ...

3
votes

0
answers

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

0
votes

0
answers

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

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

9
votes

4
answers

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

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

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

5
votes

1
answer

109
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

821
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+...

2
votes

1
answer

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

8
votes

2
answers

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

1
vote

1
answer

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

1
vote

1
answer

70
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/...

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

2
votes

1
answer

129
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

340
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

224
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

216
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

167
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

229
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

52
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

422
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

92
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

286
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

103
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

199
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

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

4
votes

1
answer

219
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

70
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

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

7
votes

1
answer

253
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

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

8
votes

2
answers

554
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

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

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

4
votes

1
answer

169
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

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

8
votes

1
answer

621
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

595
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

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

1
vote

0
answers

79
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

203
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

608
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

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

3
votes

1
answer

125
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

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