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&...
- 11
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 ...
- 25
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 ...
- 333
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 ...
- 31
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 "...
- 13.8k
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 ...
- 11.9k
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 ...
- 2,353
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,...
- 11
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 ...
- 725
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 ...
- 11.4k
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 $\...
- 851
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, ...
- 2,223
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 ...
- 395
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 $...
- 701
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 ...
- 2,769
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 ...
- 2,223
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$.
$$\...
- 10.1k
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 ...
- 24.1k
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,560
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 ...
- 43
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 ...
- 53
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$...
- 53
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 ...
- 1,834
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 ...
- 851
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 ...
- 30.1k
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 ...
- 173
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 ...
- 2,072
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 ...
- 5,507
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 ...
- 173
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 \...
- 10.1k
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 ...
- 10.1k
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 ...
- 11.9k
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 ...
- 22.8k
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{...
- 11.9k
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 ...
- 1,842
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 ...
- 2,769
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-...
- 729
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 $...
- 585
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 ...
- 11.9k
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 ...
- 8,509
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 ...
- 11
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 ...
- 11.9k
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.
$$\...
- 449
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 ...
- 2,769
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 ...
- 2,087
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 ...
- 239
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) ...
- 2,087
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 ...
- 165