Questions tagged [triangulations]
The triangulations tag has no usage guidance.
129 questions
15
votes
1
answer
616
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.5k
6
votes
0
answers
209
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.5k
3
votes
1
answer
136
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 ...
- 13.2k
4
votes
0
answers
106
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 ...
- 28.2k
2
votes
0
answers
23
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{...
- 13.2k
14
votes
0
answers
420
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,902
8
votes
0
answers
170
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 ...
- 3,001
12
votes
1
answer
738
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-...
- 779
12
votes
3
answers
872
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 $...
- 545
0
votes
0
answers
37
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 ...
- 13.2k
8
votes
0
answers
184
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 ...
- 12.3k
1
vote
0
answers
179
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
142
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 ...
- 13.2k
10
votes
2
answers
751
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.
$$\...
- 469
2
votes
0
answers
51
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 ...
- 3,001
4
votes
0
answers
161
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,147
4
votes
1
answer
2k
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
221
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,147
6
votes
1
answer
466
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
9
votes
1
answer
281
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 ...
- 91
12
votes
0
answers
133
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,842
1
vote
1
answer
258
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 ...
- 366
16
votes
1
answer
906
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 ...
- 6,290
13
votes
1
answer
899
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 ...
- 10.5k
4
votes
2
answers
486
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 ...
- 141
2
votes
0
answers
87
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 ...
- 3,079
3
votes
0
answers
102
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_{\...
- 2,789
3
votes
2
answers
323
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 ...
- 151k
5
votes
0
answers
226
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 ...
- 8,723
9
votes
3
answers
403
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=\...
- 3,001
6
votes
1
answer
153
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-...
- 17.4k
6
votes
2
answers
159
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 ...
- 19.1k
6
votes
1
answer
228
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 $\...
- 151k
7
votes
2
answers
187
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 ...
- 109
4
votes
1
answer
172
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 ...
- 24.7k
2
votes
0
answers
138
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 ...
- 781
20
votes
0
answers
540
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
254
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 \...
- 81
1
vote
0
answers
25
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,...
- 13.2k
1
vote
3
answers
941
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
326
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
742
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}...
- 37.8k
3
votes
0
answers
387
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, ...
- 109k
5
votes
1
answer
272
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 $...
- 10.1k
8
votes
3
answers
261
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 ...
- 1,579
5
votes
1
answer
261
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 ...
- 151k
4
votes
1
answer
171
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 (...
- 3,376
2
votes
0
answers
104
views
Existence of triangulation of Lipschitz domains
Consider a bounded Lipschitz domain $\Omega \subset \mathbb R^n$.
Q1: Can its closure $\overline\Omega$ be triangulated?
Q2: If yes, can the triangulation be chosen as finite? Furthermore, how ...
- 5,327
12
votes
4
answers
2k
views
What is the number of equitriangulations of the n-cube?
I wonder if this question has been considered before and if anything is known. My search attempts have failed so far.
Let's consider the n-dimesnional cube, $[0,1]^n$, and let's call a simplex with ...
- 85.6k