# Questions tagged [triangulations]

The triangulations tag has no usage guidance.

81
questions

**4**

votes

**0**answers

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

**14**

votes

**1**answer

525 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

159 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

184 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

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

**2**

votes

**0**answers

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

**0**

votes

**0**answers

14 views

### Rationale behind partitioning heuristic for Euclidean MWTs

Finding Minimum Weight Triangulations of planar pointsets is NP-hard, whereas it can be solved in $O(n^3)$ with backtracking for simple polygons.
A fairly popular heuristic for calculating ...

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

291 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

141 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

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

**9**

votes

**3**answers

588 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

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

**7**

votes

**0**answers

160 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

82 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

62 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

612 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

41 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

122 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

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

**2**

votes

**0**answers

165 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

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

**8**

votes

**0**answers

124 views

### Is every compact smooth Riemannian manifold bilipschitz equivalent to a finite simplicial complex?

Let $M$ be a compact smooth Riemannian manifold. Then it admits a triangulation, i.e. a finite simplicial complex $K$ which is homeomorphic to $M$. Any such simplicial complex carries a natural metric ...

**12**

votes

**0**answers

117 views

### Finite list of neighborhoods to approximate any finite simplicial complex

It is easy to see that any (locally finite) graph is homotopy-equivalent to a trivalent graph. Moreover, this can be achieved by a local construction - take neighborhoods of vertices of degree $> 3$...

**1**

vote

**1**answer

148 views

### A totally geodesic triangulation

Let $M$ be a compact orientable $n$ dimensional Riemannian manifold.
Is there a triangulation of $M$ such that every $k$ dimensional face of each simplex is a totally geodesic submanifold, $\forall k ...

**16**

votes

**1**answer

801 views

### Can one determine the dimension of a manifold given its 1-skeleton?

This may be an easy question, but I can't think of the answer at hand.
Suppose that I have a triangulated $n$-manifold $M$ (satisfying any set of conditions that you feel like). Suppose that I give ...

**8**

votes

**1**answer

599 views

### Critical dimensions D for “smooth manifolds iff triangulable manifolds”

I am aware that at least for lower dimensions,
"smooth manifolds iff triangulable manifolds"
at least for dimensions below a certain critical dimensions D.
My question is that for
For ...

**4**

votes

**2**answers

137 views

### Complexity of Random Delaunay Triangulation in 3D

My question:
Is the number of cells in a three-dimensional Poisson-Delaunay triangulation with $n$ vertices $\mathcal O(n)$ with probability one?
which is equivalent to the question
Is the ...

**2**

votes

**0**answers

81 views

### Existence of a “generic enough” lattice point interior to a lattice triangle

Let $T$ be a lattice triangle in $\Bbb R^2$ (i.e. the convex hull of three noncolinear points in $\Bbb Z^2$), and assume it has at least one interior lattice point. Is it always possible to find a ...

**2**

votes

**0**answers

89 views

### Find a certain triangulation subordinate to a given covering of a manifold

Let $\{U_\alpha\}$ be a covering of a smooth manifold $M$. Replacing it by a refined covering if necessary, we may assume some good properties of it, like, (1) any intersection $\cap_{i=1}^k U_{\...

**3**

votes

**2**answers

248 views

### Minimum weight triangulation of lattice points in a circle

Let $r$ be a natural number, and consider the $\mathbb{Z}^2$ lattice points
$S$ inside or on the circle $C$ of radius $r$ centered on the origin.
Let $P$ be the convex hull of $S$; so $P$ is inscribed ...

**5**

votes

**0**answers

208 views

### Are there non-cuspy triangulations of smooth manifolds?

In (as it turned out my misunderstanding of) the literature, a "smooth triangulation" seems to mean: a homeomorphism from a simplicial complex, such that on each simplex the map can be extended to a ...

**9**

votes

**2**answers

265 views

### Are there invariants of cell complexes similar to the Euler characteristic?

The Euler characteristic is an invariant (under homeomorphism) of manifolds that can be computed from a cellulation by (weighted) counting of different kinds of objects, namely
\begin{equation}
\chi=\...

**6**

votes

**1**answer

138 views

### Combinatorial curvature of real projective plane

There is a notion of combinatorial curvature due to Forman, see here (published paper) or here (preprint). I checked for a couple of small triangulations of $\mathbb{RP}^2$ (6-vertex, 7-vertex, 9-...

**6**

votes

**2**answers

135 views

### Eberhard-type theorems for Fisk triangulations?

A triangulation of a surface is called a Fisk triangulation if the degree of all but two vertices is even, and these two exceptional vertices of odd degree are neighbors.
I would like to know what ...

**5**

votes

**1**answer

152 views

### Does this iterated Delaunay triangulation process always “explode”?

Let $P$ be a set of three noncollinear points in $\mathbb{R}^2$.
Iteratively form the
Delaunay triangulation
$\cal T$ of $P$, and then
augment $P$ by the circumcircle centers of all triangles in $\...

**7**

votes

**2**answers

147 views

### The number of $2$-simplices and the number of $1$-simplices in a $4$-dimensional simplicial complex

Given a $4d$ simplicial complex (a triangulation of $4$-manifold), is there any relation between the number of $2$-simplices (triangles) and the number of $1$-simplices (edges)? Generically, is the ...

**4**

votes

**1**answer

161 views

### The number of simplicial and general $d$-polytopes with $d+3$ labelled vertices

Micha Perles used Gale diagrams to compute the number of simplicial $d$-polytopes with $d+3$ vertices and of general $d$-polytopes with $d+3$ vertices. The computation can be found in Chapter 6.3 of ...

**2**

votes

**0**answers

93 views

### Does any smooth oriented closed orbifold have a fundamental class

This thread:triangulation of orbifolds
has shown that any smooth closed orbifold has a triangulation. My further question is: if the difference of any two triangulations $P$ and $Q$ is a boundary of a ...

**19**

votes

**0**answers

509 views

### Homeomorphisms of the sphere mapping a geodesic triangulation to another one

Consider the standard Riemannian 2-sphere $S$, equipped with a geodesic triangulation $T$. Let $L(S,T)$ be the space of homeomorphisms of $S$ which map
$T$ to a geodesic triangulation. What is the ...

**1**

vote

**0**answers

143 views

### Interior and boundary vertices of weighted graphs

Xu He's article Rigidity of Infinite Disk Patterns and I have a problem with a statement he makes on page 7.
He considers weighted embedded planar graphs $G=(V, E)$ with weight function $\Theta: E \...

**1**

vote

**0**answers

21 views

### Finding Equal-volume Triangulations in Homogenic Coordinates

Given the $n$-dimensional triangulation $\mathbb{T}^n$ of a finite set of points $\{p_1,\ ...\ ,\ p_{n+k}\} \subset \mathbb{R}^n$, is it always possible to find $n+k$ positive real weights $\{\omega_1,...

**1**

vote

**3**answers

639 views

### How to do a clockwise ordering of a planar graph in order to define its faces?

I am currently making an algorithm for planar graphs that I need to triangulate so they become maximally planar (that is triangulated and planar) given only the lists of neighbors for each node : no ...

**11**

votes

**2**answers

260 views

### Triangulation with simplices of same volume

Let $M$ be a Riemannian smooth compact manifold.
It is known that $M$ has a triangulation, for any dimension. But do we know if there exists a triangulation such that all simplices have same volume ?
...

**10**

votes

**0**answers

671 views

### Can any smooth triangulation of a smooth manifold be blurred?

For the purposes of this question, let's say that a blurring
of a smooth triangulation $T$ of a smooth manifold $X$
is a smooth homotopy $h\colon [0,1] \times X \to X$ such that $h_0=\operatorname{id}...

**3**

votes

**0**answers

274 views

### regular triangulations of the product of two simplices

Is description of all regular triangluations of $\Delta^n\times \Delta^k$ known? (Regular triangulations are those which correspond to vertices of Gelfand--Kapranov--Zelevinsky secondary polytope, or, ...

**5**

votes

**1**answer

249 views

### Is every triangulation of a Euclidean ball by convex tetrahedra shellable?

Suppose you are given a 3-ball $B$ in $\mathbb{R}^3$ that is bounded by a PL sphere, a triangulation $T$ of $B$ by Euclidean tetrahedra. Is that triangulation necessarily shellable?
I know that if $...

**8**

votes

**3**answers

223 views

### Colorings of triangulations as a generalization of the four-color problem

My question can be viewed as a generalization of the four-color problem. Instead of a planar graph, consider a triangulation of a d-sphere. One wants to color vertices with N colors so that no two ...

**4**

votes

**1**answer

222 views

### Do random triangulation edge-flips maintain randomness?

Let $S$ be a fixed set of $n$ points in the plane in general position.
Let $T$ be a triangulation
of $S$, (somehow) selected
uniformly at random from all triangulations of $S$.
(There are an ...

**4**

votes

**1**answer

152 views

### Geometric realization of an abstract triangulation of the plane

Can every abstract simplicial complex whose geometric realization is homeomorphic to $\mathbb{R}^2$ be realized by a rectilinear triangulation of the Euclidean plane? Alternatively put, can a curvy (...