# Questions tagged [triangulations]

The tag has no usage guidance.

124 questions
Filter by
Sorted by
Tagged with
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 ...
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$ ...
• 123
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,906
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}$ ...
• 346
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 ...
• 131
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 ...
• 75
1 vote
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
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 ...
• 469
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
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
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 ...
821 views

• 1,209
1 vote
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, ...
• 2,480
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 ...
• 395
219 views

• 10.4k
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.4k
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 ...
• 12.7k
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 ...