Questions tagged [triangulations]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4
votes
0answers
120 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 ...
14
votes
1answer
525 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
0answers
159 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 \...
6
votes
0answers
184 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 ...
3
votes
1answer
49 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 ...
2
votes
0answers
70 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 ...
0
votes
0answers
14 views

Rationale behind partitioning heuristic for Euclidean MWTs

Finding Minimum Weight Triangulations of planar pointsets is NP-hard, whereas it can be solved in $O(n^3)$ with backtracking for simple polygons. A fairly popular heuristic for calculating ...
2
votes
0answers
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{...
14
votes
0answers
291 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 ...
8
votes
0answers
141 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 ...
9
votes
1answer
164 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-...
9
votes
3answers
588 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 $...
0
votes
0answers
29 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 ...
7
votes
0answers
160 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 ...
1
vote
0answers
82 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 ...
3
votes
1answer
62 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 ...
10
votes
2answers
612 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. $$\...
2
votes
0answers
41 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 ...
4
votes
0answers
122 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 ...
4
votes
1answer
281 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 ...
2
votes
0answers
165 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) ...
6
votes
1answer
357 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 ...
8
votes
0answers
124 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 ...
12
votes
0answers
117 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
vote
1answer
148 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 ...
16
votes
1answer
801 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 ...
8
votes
1answer
599 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 ...
4
votes
2answers
137 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 ...
2
votes
0answers
81 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 ...
2
votes
0answers
89 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_{\...
3
votes
2answers
248 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 ...
5
votes
0answers
208 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 ...
9
votes
2answers
265 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=\...
6
votes
1answer
138 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-...
6
votes
2answers
135 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 ...
5
votes
1answer
152 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 $\...
7
votes
2answers
147 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 ...
4
votes
1answer
161 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 ...
2
votes
0answers
93 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 ...
19
votes
0answers
509 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
0answers
143 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 \...
1
vote
0answers
21 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,...
1
vote
3answers
639 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
2answers
260 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
0answers
671 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}...
3
votes
0answers
274 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, ...
5
votes
1answer
249 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 $...
8
votes
3answers
223 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 ...
4
votes
1answer
222 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 ...
4
votes
1answer
152 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 (...