Questions tagged [triangulations]
The triangulations tag has no usage guidance.
129 questions
4
votes
1
answer
196
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$...
- 28.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.
$$\...
CommunityBot
- 1
8
votes
1
answer
618
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 ...
- 32.1k
1
vote
1
answer
51
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 ...
- 7,226
1
vote
0
answers
87
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,275
5
votes
0
answers
214
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 ...
- 7,545
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 ...
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 ...
- 37.8k
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 ...
- 151k
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
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-...
- 2,479
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
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 $...
- 10.5k
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 ...
- 63.9k
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 ...
- 151k
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 ...
CommunityBot
- 1
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 ...
- 45k
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) ...
CommunityBot
- 1
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 ...
- 10.4k
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 ...
- 91.8k
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 ...
- 85.6k
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 ...
CommunityBot
- 1
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 ...
- 18.6k
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
14
votes
1
answer
908
views
Comparing layered triangulations of 3-manifolds which fiber over the circle.
I am sorry but I am reposting this question because I wasn't logged in when I first asked it.
Ian Agol has produced a method to build an ideal layered triangulation of a hyperbolic 3-manifold which ...
- 68.9k
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 ...
- 7,276
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
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-...
- 1,593
17
votes
1
answer
582
views
Finite union of closed convex sets is triangulable?
I posted this question on math.stackexchange.com, but didn't get an answer.
Let $A_1, \ldots, A_k \subseteq \mathbb{R}^n$ be closed convex sets. Is the union $\bigcup_{i=1}^k A_i$ triangulable, that ...
- 13.6k
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 $\...
- 13k
4
votes
1
answer
323
views
What properties does generalized Delaunay triangulation have?
Suppose that instead of the usual circle, we pick some other convex set D and make the Delaunay triangulation of a finite planar point set with respect to this set, i.e. connect two points if there is ...
- 4,713
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 ...
CommunityBot
- 1
9
votes
1
answer
424
views
Hamiltonian circuit
Let us consider a disk with one labelled point on the boundary and $n$ labelled points in the interior.
Let T be a triangulation of the whole disk with vertices on the labelled points such that T ...
CommunityBot
- 1
5
votes
6
answers
435
views
Characterizing Convex Configurations of Quadrupels of Coplanar Points via Linear (In-)equalities between Distance Sums or Differences
Given 4 points $A$, $B$, $C$ and $D$ in general position in the euclidean plane, is it possible to determine from the 6 distances $AB$, $BC$, $CD$, $AD$, $AC$ and, $BD$ alone, whether every point is a ...
- 4,713
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 ...
- 315
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 ...
CommunityBot
- 1
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 ...
CommunityBot
- 1
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 ?
...
- 13.6k