Skip to main content

Questions tagged [triangulations]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
Denis Gorodkov's user avatar
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$ ...
Shiquan Ren's user avatar
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 ...
shuhalo's user avatar
  • 4,906
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}$ ...
Vadim's user avatar
  • 346
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 ...
Maaz's user avatar
  • 131
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 ...
Kregnach's user avatar
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, ...
Kregnach's user avatar
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 ...
Till's user avatar
  • 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-...
Kregnach's user avatar
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 ...
Igor Makhlin's user avatar
  • 3,493
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 ...
Jose Antonio Martin H's user avatar
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+...
interstice's user avatar
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 ...
Manfred Weis's user avatar
  • 12.7k
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 ...
Kregnach's user avatar
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$...
Manfred Weis's user avatar
  • 12.7k
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/...
Nandakumar R's user avatar
  • 5,611
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&...
PatL's user avatar
  • 11
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 ...
P.Labarque's user avatar
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 ...
Mike's user avatar
  • 335
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 ...
rab's user avatar
  • 159
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 "...
aglearner's user avatar
  • 14k
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 ...
Manfred Weis's user avatar
  • 12.7k
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 ...
Calvin McPhail-Snyder's user avatar
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,...
Fran's user avatar
  • 11
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 ...
CambridgeStudent's user avatar
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 ...
Hao Yu's user avatar
  • 771
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 ...
M. Winter's user avatar
  • 12.7k
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 $\...
G. Blaickner's user avatar
  • 1,209
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, ...
Stéphane Laurent's user avatar
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 ...
Joaquin Lema's user avatar
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 $...
B.Hueber's user avatar
  • 1,077
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 ...
Andi Bauer's user avatar
  • 2,911
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 ...
Stéphane Laurent's user avatar
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$. $$\...
wonderich's user avatar
  • 10.4k
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 ...
Gil Kalai's user avatar
  • 24.2k
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, ...
Student's user avatar
  • 5,038
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 ...
Bruno's user avatar
  • 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 ...
Zhengdi Sun's user avatar
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$...
Zhengdi Sun's user avatar
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 ...
Agelos's user avatar
  • 1,884
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 ...
G. Blaickner's user avatar
  • 1,209
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 ...
Hailong Dao's user avatar
  • 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 ...
Scattering State's user avatar
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 ...
Jose Capco's user avatar
  • 2,185
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 ...
Dmytro Taranovsky's user avatar
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 ...
Scattering State's user avatar
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 \...
wonderich's user avatar
  • 10.4k
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 ...
wonderich's user avatar
  • 10.4k
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 ...
Manfred Weis's user avatar
  • 12.7k
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 ...
Sam Nead's user avatar
  • 26.6k